CT62077

Last ledgers of Pavel

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the dune sea of Caravanrest; Pavel weighs the day's ledgers manifests and starts the calculations. 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: 2830 401558306 482881090 2989803 978098342 822373933 586647160 275325082 220080724 691418318 527150681 114811750 816447579 904575695 960114815 491907300 664338032 852243209 431627375 106481417 648138728 900964814 432691122 622092819 162183013 499183343 230800306 756787204 599352716 125932095 150248471 848677038 928774097 84071643 921438487 172829220 94434718 6659848 918735348 199278281 121147962 624901308 729344698 67706856 533587847 900151789 703938810 612141367 408433707 445254896 131693057 765395503 886480138 338115129 676818302 484776620 240759216 575127222 208422288 499042 690523040 347021055 210929861 326574652 57714970 733273394 372182435 803332195 76362930 280042142 878998992 778399571 382453875 465145493 871506109 889285210 986073829 495620689 971898105 262382892 567614276 4144568…
Output: 11333011350

Example 2:

Input: 1963 673010244 478061177 224740671 544607591 578760529 181338584 189218780 7106136 601774236 29868366 290206635 726381155 616613959 654875305 385277010 125314752 23371776 300075528 927669574 880418248 800748758 846976408 657511636 374030415 595123575 982380980 487352875 791912424 134537365 42616835 850512904 464316266 272680393 549187207 852593557 898735149 9630358 875235384 858265894 333956513 458864393 129721643 165649156 51604156 792836825 219704152 46204286 8434912 933621416 228257454 85907282 622986649 125743874 6318897 863496617 142543693 884563968 482335895 163701400 134729797 927902345 527897804 250382770 723992359 670421241 880133180 761083714 880929326 183741861 661967516 612312107 328953141 934688102 344154638 207334333 405102796 256942451 351789819 42741078 486909206 773122120 …
Output: 7628498455

Example 3:

Input: 1684 352502449 25282405 794300113 533859768 693957236 721885956 795862027 488262640 595353613 28527033 813259267 12898983 931286080 745839243 516797439 890861700 81675176 4267588 531465608 141719367 714413811 61289388 40459539 919029091 734026799 438441447 389924615 564687753 584780810 657051059 616987937 34160756 226403668 65805846 40836222 456999058 380628682 222466063 976924649 342965621 913589101 286334176 972297603 425432110 692190870 398055479 478628300 138306142 262742989 131593556 20411008 992774387 44424281 978612333 509817330 246033908 329251904 201646844 958947761 468931802 925664903 778424666 782218979 226324075 260065245 685643966 718016965 234835888 497844014 606231304 685487855 840054135 410169599 41544270 319365437 871874110 193845998 718868909 459185078 213708728 732289161…
Output: 7317780148

Constraints:

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

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