CT60384

The marks at Cindercrag

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wasim the surveyor watches over the ember mines of Cindercrag's stores of marks. A careful computation stands between order and chaos. 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: 3548 325402860 577568957 755236116 231608538 575127577 526819272 862825661 658053134 86974953 237134517 353238226 144076622 948231842 497633557 552939313 33491162 49504470 80405 88775487 426623292 342457030 496913873 610739314 395692386 216719915 693036790 438568723 920017693 156441373 975326697 767045635 168530305 399187575 918832273 693028634 207925045 171342528 384692353 644352830 210354557 866787146 144589912 351894524 356524357 354992704 80824878 810969222 424527843 244584998 229784071 735667433 756097360 369143296 607532988 364680294 783239820 503256207 948577721 430115113 642976741 251949544 645615985 274822816 391385456 18386730 519626795 349721704 52815591 49316617 594155291 274211056 142092703 522088694 159479346 555738064 244786427 229772697 278247099 707139206 173363916 8604269…
Output: 9817950077

Example 2:

Input: 3047 761704957 296693247 279161871 201094377 190542810 556000011 139356678 885346893 841652903 278233482 791569467 677554170 502272079 873498472 101282589 567817763 741475054 616952315 723279418 297073090 200701166 614648324 196728140 377779418 903748542 883239297 564009195 626601206 792882582 416814299 261797056 422961689 986652040 724672444 534111745 894015249 540218741 118948873 930994141 54312752 214028123 62163450 879017566 813310664 646267923 286110711 148527189 283442278 461201707 240038348 51581377 952852072 548468292 89350716 616284845 835284364 763097683 898262937 96130686 67036356 364509637 646797330 797864301 279509591 606868079 876448396 316136601 72880431 879883528 667834649 41880607 255738712 692185961 190810737 463569332 411674452 368417999 675189210 74534262 484932828 4362…
Output: 8351987097

Example 3:

Input: 1039 965763203 128183534 79753300 751726028 460474629 318635868 98732819 279564935 445748696 5927245 456484148 834983060 506152773 840900267 215457576 550678489 991779435 392468899 85623762 12402493 345081903 821111548 443315336 342902425 169587535 508254686 272876452 945190319 283236187 403362091 405145795 181566263 139359575 108295103 328980913 789716658 402087323 723917985 908426919 612387492 553686063 887328173 144407716 366247403 726809217 255748864 84025355 851782440 418789249 867778971 736615205 675373176 384787174 161429188 730343344 578758652 107286743 375590636 251614525 12863134 299691476 701183375 869921704 297733297 139295730 34951409 985199114 716447328 965583331 156927995 702942412 265005245 519222486 812248902 905932612 245832644 715416337 58934360 166049690 261538049 88769…
Output: 6228862150

Constraints:

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

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