CT58828

The Grand Facade of Scrollkeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the archive halls of Scrollkeep opens only for a perfect tally of signals. Milo means to find out. 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: 1229 48037823 922041426 528489129 309258001 680514820 27777131 258155813 375473011 65363034 932150011 831499760 209441658 992029850 909494044 782164616 330033587 974973391 297681760 348198280 50675376 12896941 433936747 726630594 954758718 438210578 33063829 60072685 192378552 767041070 222101934 966356293 625085421 965257220 617348627 524717204 620299974 673504807 912174418 942317937 126538252 515476600 751700273 406502083 237439871 564122567 288483765 588103855 431660223 313082451 478603211 175187612 161309586 204145069 290666575 332714581 350516493 748798342 106094346 50264302 148564743 814225340 305586613 773311830 378442735 390821246 82050748 980712800 841875980 229306519 93176487 679704637 240200996 487090209 147203306 608445276 996559515 881384175 261348526 680460396 891005269 54839…
Output: 7170393972

Example 2:

Input: 3142 946462028 529477184 439392000 959501746 774828794 497605200 186757253 734558252 379514297 162590215 171582038 45587372 309030158 457359058 420817971 394276357 811177889 47897745 762844009 671722110 840206889 287401360 201253566 458839191 393505411 896224341 15430090 957748016 777499416 545001206 590232823 241447115 695326977 496794844 402174377 592055075 777406509 284044749 335521622 659873524 571944262 687604208 442511812 765442778 157135816 93305643 875960430 167893572 883303088 449144523 624357313 668630 996375488 655722266 768660000 984343418 72907175 591768982 679961131 895763783 666083006 276182157 833498410 57269679 749171867 70001921 499775029 171760875 608706226 570087802 986403165 532422117 67001671 51205819 466234292 216001708 467996019 245200188 853955003 772583446 4437185…
Output: 9099172904

Example 3:

Input: 582 551662865 172753716 809061799 331211893 572110146 847174330 684386524 378936108 798172598 764093763 814857955 614045478 10023130 114048322 908957152 394190757 201819313 463197238 795799068 763834575 690059937 901066943 145083133 960658704 726298611 946658597 561044409 742334057 125495915 913722707 588959126 7223313 438231112 914109901 355869296 959652874 899612177 916330392 565332479 357318465 596720113 380439427 85241038 689674667 521227 850760681 786698174 107712421 79245803 335373291 703267789 208373798 427809930 911550526 342792292 49610978 860138602 555072280 906453009 795512943 479753835 348032721 329809442 322718828 763526193 780160278 753859530 450206817 117605036 250292027 32483661 520981531 460356746 40276797 516154484 780294964 564191042 604545846 89405808 681818576 21178818…
Output: 6884003826

Constraints:

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

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