CT58304

The Grand Facade Beneath Bloomglass

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the orchid house of Bloomglass close for winter, Fiora must finish the signals ledger - one figure at a time. Task: Bars of heights h[i] stand side by side with width 1. Print the largest rectangle area that fits inside the histogram. Input format: First line: n. Second line: n heights. Output format: Print the maximum area (fits 64-bit). Constraints: 1 <= n <= 4000; 0 <= h[i] <= 10^9.

Example 1:

Input: 2096 685639703 900096726 670072097 9073054 485813614 836737367 817545938 390922287 303354790 431086013 264876723 147858829 594758683 874419417 18122377 594622222 587541146 294853697 871140315 486555490 697183960 744806124 724308636 874220555 84420719 641096529 52035764 359874975 971786720 595120673 256422432 987647064 689387068 191380018 833854212 444073193 707998845 882241318 400735508 904441426 719697208 392677895 422264483 694488421 855755136 814971190 770567439 31689728 611049608 829080022 127308642 304228708 125169478 676757452 366457783 566756928 686752838 781842376 982857222 634934145 412341518 860469705 962335097 328410739 341500450 731813061 999960769 17831277 61944579 837166304 791046882 235403674 103281706 567310153 486015289 920185118 750442526 784227875 426341265 964587704 273…
Output: 6487494340

Example 2:

Input: 1088 896093479 260493365 782978426 919090508 843634176 975809768 360657480 110013604 295780236 262421719 563317649 990547725 787297048 943175604 73620190 714846832 497112795 206271957 511116355 687645337 715151954 135619161 314437859 53638699 563334850 527488925 209882538 862387502 460992201 720376993 396155211 753586056 689884756 819564769 14329183 433031767 430683658 284866267 348415301 316685451 1196074 11006599 854000168 675640821 472036341 804655332 244100997 655673330 305412879 681245734 579524712 329687248 236331707 740122282 650475086 591975749 693374540 604721377 480980738 460625279 879276792 437587764 52678038 134082374 533306430 993278467 886610801 269536591 200593422 530244593 788882237 654421337 720962361 814981029 21548980 970246860 887244772 50280352 502212213 874801186 9715…
Output: 12039000576

Example 3:

Input: 3053 159306153 536506553 636161171 593249336 849827491 966592906 647802299 993852126 973781581 631171042 287804529 699227354 634940188 298911589 268325943 457135717 97112022 514145948 30600968 848745059 402719799 766409757 728126397 380896963 80632451 942432414 171680079 389798690 304696713 84967461 778545887 276913266 459963707 526557391 216404851 971885770 967817051 983606944 991787495 522731481 335882012 540145622 288275157 838409562 148518717 940893521 647402178 162331708 617601536 597321422 782411903 963926594 63464544 289646000 241465635 967538768 252782730 65017711 637525922 336035075 561049253 597251130 306932011 999871131 498439055 679268082 807416400 419340105 768644001 449536698 760259145 678591953 593062898 821358903 437096244 278044036 276476640 123479063 789353314 752179380 2…
Output: 7346777360

Constraints:

1 <= n <= 4000; 0 <= h[i] <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.