CT58231

Quinn's ledgers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the quays of Driftwood close for winter, Quinn must finish the ledgers ledger - one figure at a time. 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: 3379 797470816 428252034 644674431 427090301 968423824 840011384 22143670 356140508 177432863 603651687 211385429 853298852 141761110 406036241 134462230 363795723 477105608 285399004 201607297 551827498 794887334 501816738 627375445 255118822 241260072 569579241 240601390 585565063 422901494 768840152 471651284 418659494 16457422 437850148 380418516 622112120 314434978 422837096 50906430 698163275 492517570 163716918 806831154 167639536 861373298 993447827 239893730 134444391 857968950 769734699 227540016 46583217 630913116 79816907 242868430 358743783 843099649 209448766 618286308 2240235 18706984 346589707 628802379 807382367 519767888 523204220 438659626 450644033 138010307 831901022 413035289 21675440 800888172 162948692 341504377 199591692 409077276 453842507 181580540 561299075 7404…
Output: 7477377133

Example 2:

Input: 1530 282735429 211843681 185348113 53984153 605323524 675505747 940994589 793647723 971350617 841752872 454708398 737851620 707784382 5102539 371963149 232807852 772079983 815848796 191548029 963912189 327686877 735553161 521325917 676427584 153948140 615834320 196077887 649906535 87296391 283812364 292322370 304876702 851511424 876276987 128716289 721777732 312283114 285052753 462121149 191246155 321012834 707079278 359005378 739880597 730083004 900690397 757159089 45838414 551500286 273422769 798627896 893589044 915696420 88441154 616355069 223584725 570107378 245446020 513690348 978209252 781249893 431315751 55801420 438452576 257281788 368679819 75985980 21504608 789952658 845005738 81365054 724984694 92503375 693821587 442406851 125618408 382319618 357994146 313070880 845540479 678958…
Output: 6954587120

Example 3:

Input: 1239 790239228 762106797 35096860 284827903 274756131 58107395 880002530 51479820 380570864 135439932 11137923 692778554 819245816 400705655 673083789 349673914 529260756 690268353 158716057 790163613 361125316 343352377 577099006 168810078 825320515 176618431 102039751 20305332 522411445 406267003 626444467 113565520 772375481 578514082 1810723 442235057 823649099 32748959 16857833 150612441 596401325 203243054 774744266 808314669 502020517 577095857 404343998 863959306 484899199 208740007 18148143 566509357 136430749 203444473 595116443 806742664 521611961 699520567 628882208 297394449 168082318 49623695 259720463 517922238 400744110 75949202 65432233 258453447 299914229 105377951 575390641 286277839 521016919 880511524 126697676 512531174 174966034 536604834 19918277 271598437 364349664…
Output: 7238637912

Constraints:

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

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