CT64776

Cleo's Quiet Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the ribbon falls of Cascade Vale, someone must balance the workshop's books. This year the task falls to Cleo, armed only with the registers register. 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: 479 146953801 742810171 191673273 707013421 483884793 624485319 542219718 325610392 45123450 518740280 899002155 216540093 225473716 788255399 807669619 911681121 393556742 958738451 659653466 284697011 91892011 595742402 326694086 8773662 528226382 454784200 844775798 93857032 636379365 594969174 16109505 998013601 714803948 607240376 576692966 122752977 819217229 642119994 755707187 785796458 550366587 609652125 37209295 95187929 325451685 107577473 703188767 860436402 638994889 220835909 868562221 798486362 285741974 140749494 743145915 63220844 590852553 674571506 682638434 3370325 718312704 811383181 566948794 136818250 856757293 974328382 241129787 984480695 978093366 756230001 746705138 790705254 642638248 988575643 742898660 452424083 408127511 459759518 198442672 208101520 5885864…
Output: 9518299911

Example 2:

Input: 2728 520901845 169441595 746766347 897174520 346597964 506411200 393775796 571211485 599431257 492735644 20606473 790189451 470770785 950295228 250780873 887137979 607184188 885312333 335677023 223989995 313379462 668115223 629002993 787480970 722554654 277806032 315047707 76225097 517569495 354707859 601707493 130215927 724211719 370431354 410223281 806156152 479310698 298629778 760831696 653364084 119766420 869562500 126352115 661650789 426659005 480540203 20058620 637293374 250346859 143772322 774996392 439577079 734675200 526450319 422396561 289186284 992556833 772806043 81504027 150755150 473782607 455696214 590690916 115531826 911742901 510707305 809593083 583284891 394472914 208882435 797228304 124606602 499753848 386646399 97799860 642409133 301983132 532752909 361518261 433345403 …
Output: 8359414161

Example 3:

Input: 1018 591849672 480176913 95523390 384794106 916342242 483333456 105782816 977950374 492604225 480325725 655237466 351035536 594469438 883903203 228540063 457060108 243185845 895640912 742540658 889057144 714111750 343035841 787375212 227375994 965317673 350084598 386308231 348225728 645078194 302426790 444339585 410772114 780798709 602600722 896219336 582220976 858026752 566048418 724063612 46051894 818709796 157309148 651871512 494622988 281695670 84597503 161970168 675681446 257692794 432463018 247295209 646213033 690780230 956589344 568572669 909919749 392093576 348609681 495691630 860066380 846040774 988858964 694687246 431332933 659586939 282039652 669720917 327286392 206728784 396157431 941547650 674664160 994272021 847035895 159624105 526536863 355254640 863266160 166524145 61184280…
Output: 8110398233

Constraints:

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

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