CT59845

Odin's Silent ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Odin runs the apiary at the honeycomb cliffs of Beeswick. Today the books show a list of ledgers, 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: 3644 784617619 883042119 212782429 156066402 151184265 129045275 818199055 432898951 952288490 699132233 348172130 276938757 127225572 674936058 396254810 879363131 441700305 982416334 597374498 625770977 336857985 883082717 898781305 53515034 528553153 91997799 885513690 722779906 744678121 731375607 182106715 636468285 628149850 37596970 429519929 721800004 89115770 896336629 684288144 666722212 723394122 300884441 418639731 245652422 376782963 400042285 685538041 156888095 394077367 481572605 174288093 289764830 795135338 173123002 939042655 925523876 685193647 959517391 989035782 943807303 672603610 214670680 468588359 258811988 684820308 52740404 271865050 418571154 258355583 316677707 17071561 322837496 811284143 776407252 364828464 273787796 896606250 212339121 299684422 514151726 8…
Output: 8712924288

Example 2:

Input: 1548 581847703 265046391 438995804 794170053 2967114 649838210 4030844 543885692 186503432 112959974 20888309 737323376 406934732 369244242 578769592 725091768 197575702 155404896 150391008 717742433 524736762 497233640 217146097 291853065 47388647 983787551 285404368 4077696 785316194 754904831 310270457 119741551 640083592 774343159 217223425 389368664 193302922 672283686 565970140 36412975 552107437 995070196 734003975 577977508 647072026 190493606 147430846 502313995 932748247 120586822 14438302 562788983 105878381 346961789 889046171 397560462 9482520 311378269 631769818 211359092 257031151 253305150 330591813 854960833 873248467 885715429 424113109 901034814 529889056 973141902 957016375 236967995 868324254 706846052 567279663 136427204 315080236 782464571 655927088 494048764 5598472…
Output: 6257731118

Example 3:

Input: 3915 751924696 304379394 837555989 119101266 364504337 295475777 291411750 118500267 541360580 122337507 494288012 640509335 900778213 343369018 368134417 478551552 253208959 444421750 320517077 635246040 973162613 979801633 500791922 305184662 582055469 828548569 342649337 449596866 831582281 711815948 76023910 521508519 723376584 589022345 583511013 168930586 382538675 116106732 65729193 128443318 83653155 865673662 135413469 514897413 461733376 627436978 309188319 320989894 312071258 311109350 341968690 299578782 935764575 180162323 12897974 611392782 704371485 564504925 365396405 77797458 746045689 720569747 307242202 154018833 385520927 383497324 654838578 822662303 445748807 109612190 762120543 783114577 34037932 592934411 37281806 313968432 702555154 974395986 985116689 46143723 836…
Output: 10665934074

Constraints:

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

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