CT61631

Pale ledgers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the monsoon port of Rainhaven, Cleo records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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: 2074 56004897 826672473 352604270 226445944 353631681 982362713 656200721 367767307 2957605 904746049 581666257 907634115 521173512 747057614 477714575 543168842 271549786 610254348 786920337 622040829 46215318 280578512 674868801 360767703 104540275 735699278 130511603 363699922 371574370 667328458 24279282 345509485 623641162 10751005 310042940 312470525 791452233 153383473 661439381 389078050 330945225 10555163 77207272 304046635 908916414 386707319 683246032 93759535 811977791 545260250 159090436 814374235 673757237 897386108 933991189 903355945 25749680 822017622 665793717 553621130 626614634 680769342 347446468 72069877 516769970 299707624 49089381 909432332 780853044 795511311 214892389 49122592 176459482 41848885 634959281 109893831 231656913 297444527 186538278 111477438 157038812…
Output: 9195623748

Example 2:

Input: 744 272986359 701991460 995617503 646567056 669587210 787141083 353704267 475259763 588991330 709629028 709553986 21010737 661323922 172565188 653100063 898829796 957965255 986529307 801682261 462008550 823191973 707048984 870126851 29083961 574568163 864108978 786740813 177676666 359303715 512607185 901480670 27111373 859138339 812913142 637309549 838277328 304823039 574398142 798613317 79049353 920402432 921659213 665928901 63266908 518705769 418043695 461318701 862640315 407701988 329309466 655483363 290558725 941549300 436361148 321759308 198976271 707363894 516589089 34552556 329112997 985876075 217926128 879049796 758768866 512155333 684627916 689382664 622010455 826778176 582815331 278680873 629967617 145978158 83566021 260965242 374612068 26407924 310519506 852180011 539770071 6149…
Output: 6336305552

Example 3:

Input: 3772 58141838 411199185 112922262 36654937 724017220 445511353 977138232 643352443 324111528 960248259 535435603 169983438 458465032 704684042 418892521 256876520 813617607 723004012 753696500 939360807 627052221 840390421 151386249 976816634 401159461 915708870 821048182 400892898 778247646 346754781 583777797 840396299 90452561 781845752 887683384 479252783 234125001 264357285 686328074 640080957 181455397 360678659 520375156 940720900 527353229 534333204 653167088 847691122 239729693 830882499 833497880 28434372 814789498 261045746 231601221 274719168 979412487 873899434 792081039 751223446 358229310 262865977 62629434 137987392 525475691 946620868 898582057 107492261 678027154 103368337 249631364 819727113 287572214 766208326 810547784 525068236 477208002 605668884 617133295 574116148 …
Output: 9400741658

Constraints:

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

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