CT59789

The signals at Skyharbor

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the floating docks of Skyharbor as Sable unrolls the day's manifest of signals. The tally will decide the next shipment. 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: 82 234929392 677625135 555657576 434770726 945598545 18398378 369664518 580031516 413621094 938649354 571090992 650150369 834868632 685607450 286241192 184548009 185511163 865000715 571389674 522442385 987322692 534969669 499963966 795193377 173074481 110345734 615498729 257833243 414502244 547626459 159247712 885418430 19827731 440941445 793548817 35266001 651126034 117030470 8816609 918539415 319866824 411176433 303431474 369464045 829512222 906740247 790432698 287868903 642274455 308144830 383678963 454503187 570184913 575289467 889464940 669768161 409053093 289333873 153134448 324133492 701858276 350204052 686356681 992489942 87598978 539732907 439263482 950730318 364982144 840562054 550318551 70214199 499277040 335025069 417045600 481368651 123337163 350439985 846912790 720719784 4361…
Output: 5469509157

Example 2:

Input: 420 92354007 990989146 487050131 767121435 374170456 189587820 353908113 314116293 86410508 653532123 254627650 480185987 122250196 11437740 696259540 718931755 858806596 532921208 653585934 276814010 388607140 234788811 958666222 398486291 840268636 770826012 747737424 722678729 436579446 497332791 435290336 105655907 990257704 785823185 852704190 470853389 160860029 420287303 376761655 473340861 157918094 42160430 317333162 346248981 926042091 202284838 61192883 49693089 106920902 373455958 865615359 816520468 519250133 583578940 701493931 450483406 622069269 396662784 720404713 374420901 714261347 924856044 910032902 198779098 362053436 171208292 710049891 492708807 880186223 547226064 5064080 480857535 945688886 257130702 176830731 725342267 959610376 168918654 117800569 531706276 9481…
Output: 5228383412

Example 3:

Input: 775 17396093 113305890 499622653 215092670 535423719 37456592 647624640 197125796 17512513 408225603 852116028 634299241 632340881 660219579 332921250 368744095 707201654 445010166 744540834 891047276 577126685 441297584 612747547 75655220 165897863 581441139 665703081 379625019 59256005 499806949 361128846 288786611 40592940 618293698 388025098 30108229 10112647 817294259 131889246 14491645 867707091 924825771 211103928 561434065 228330813 30174628 799598086 296436466 454382208 806940915 110443843 33552715 543582913 394343368 210888363 274219588 889396737 35011844 106298396 95183510 169903233 255657129 354060770 622235909 206310337 537924874 848775505 316886557 684681423 677251665 93139889 348952497 801572966 793145837 40763571 406060772 109372552 315560116 842656492 19016538 739550389 98…
Output: 9351512037

Constraints:

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

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