CT58392

The Grand Facade at Serpentis

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the jade shrine of Serpentis close for winter, Paige must finish the beacons 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: 1168 242185717 894728947 87377751 610751718 155730249 919984392 252365397 232837324 145477392 348144078 847122507 972826481 798410597 235924483 326042238 815525230 763303142 364314910 196978165 517074063 715424842 650214494 643023864 201213359 145805472 28064899 474045725 346084233 93778229 850564032 379923419 129601187 828804045 791886166 312119106 720595834 684771317 800168258 996949970 467979204 909238487 318986379 773900132 575178359 690910467 617167061 119581085 785576358 733187807 105981733 832080797 589432122 839030485 676650906 235955098 646467145 56794542 756485400 178724807 49169443 542736563 344079988 95786474 502355677 597851671 983545421 916944162 166374650 503015278 273831145 941472657 204932052 743154135 319603008 310318768 296851891 730461254 383820316 482984637 249942524 7…
Output: 7752593342

Example 2:

Input: 2401 770924131 911385663 462240929 730093080 840870139 677845431 881812105 241086676 894712716 25862720 927435159 105689791 502898328 484665251 441863151 285984827 274542816 209807969 605307773 403245882 715595825 163164033 624340189 153291178 3393114 32805734 294241836 440276648 172810305 767867641 834079646 445439362 862131723 776636651 368073053 460750982 222071244 51440079 332050691 170527866 304362503 338905133 134836937 117825244 107859634 263624339 830134626 981444226 261512684 694591135 1855566 193115672 528662641 890193115 429000775 176740704 86312774 893427710 432088197 669304577 512891170 840215199 842546140 421887982 265749453 444936787 432812178 265865624 228167022 953191573 893082260 43247927 980032052 339733615 95539929 713656227 412306413 663767055 946546291 63214501 996227…
Output: 7920371415

Example 3:

Input: 1256 381358420 732027819 393208309 287093903 823319099 735905166 859737874 607654561 295700768 29265119 73837006 584187755 997498244 378655479 434440125 569147380 312718365 212548857 763197659 965643826 181490472 299990101 87688340 409886542 111437819 42834161 627213828 805479516 495395843 878919522 214058346 370264893 352485620 323117121 883385135 649396851 135878853 468615619 87078080 970921270 451077833 173002499 724710170 166457339 463024488 543355780 521329256 911995257 488294024 760741531 994755723 900865257 796681859 343134946 109160497 4206067 944618843 103906441 744299453 165129977 336326184 691838959 242146973 726887810 139089660 842399777 426212251 372504336 922145023 142757961 630614737 527206737 314905041 417459108 133416012 28024254 267744308 290657380 63843091 589189848 4508…
Output: 6255572475

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade at Serpentis - MEDIUM Coding Problem | CodeTikki