CT58539

The Polished signals of Pia

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Pia runs the signal tower at the forest village of Briarthorn. Today the books show a list of signals, and the numbers must be worked out before sundown. 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: 54 711537499 175374690 986986963 863003636 28249378 216289778 94528762 142116410 747152389 47886546 156789340 840703176 5651633 486482620 605978003 211497566 126921715 623812112 542940979 34734766 288090244 802946659 232287794 933158471 429557029 631419543 702262756 209651737 963766483 954815610 559105446 210695211 428161515 718311064 33439378 97530344 989504553 843324820 491475580 583127879 751461403 12970198 134318414 107048235 697956863 323903533 555493640 240035382 132238663 353694302 100931834 896321506 539511708 724762356
Output: 2935124318

Example 2:

Input: 3193 672376250 323601634 924195586 278785706 300783898 432735814 539545999 368100933 812352032 258799766 203852647 597927214 417474026 298135926 862386515 535620783 903367805 741072614 560857421 403129336 302241987 823125383 75533393 927027893 60072144 901282181 799067870 547230091 230979126 292859392 893967912 55700569 873914795 634183193 442676487 340758592 257407023 53598620 494307900 446957866 875522327 360630380 787072903 302423040 775797619 390089075 906845536 302643629 155132465 114803037 925753738 287893402 714112332 518345813 988881220 425019397 99474704 703735283 768150493 778307222 448442549 104673647 753377158 766815727 618931979 493639673 55083682 799055308 428922171 392697720 196148090 937290576 804300916 385411265 782957403 364207607 110021701 553380361 464841346 654887910 3…
Output: 7958644575

Example 3:

Input: 364 332508632 471892591 120381414 239273433 58529158 130871010 923487873 293708788 330062152 601144179 855871291 16032064 356289935 826705596 294504648 551719318 60526594 904785576 293445135 341975399 292968020 294370339 577692925 457694332 890717399 436320214 776567912 554649950 283597517 433229272 296039689 498464797 411056308 914564883 457503883 673641121 920475760 297874621 473855115 844130036 326814751 694275987 502032216 36015926 854822643 622184903 184647730 812711244 648450348 493873497 558191864 639245320 417126867 344101315 402520425 275888785 234224959 468449740 247132774 700668514 174410036 852523688 768737995 922783150 895699269 570624841 117775251 966047237 513622775 839877197 748426717 110314265 330304272 24531969 434257458 714294670 965040273 346457296 480587019 594280300 7…
Output: 7373535442

Constraints:

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

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