CT63373

The ledgers at Skyharbor

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Curator runs the print shop at the floating docks of Skyharbor. 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: 604 27806477 635752060 867095216 103788042 483366637 291490991 520060 461512879 755495896 374680861 338090920 165770416 369620002 535933230 974706680 619404848 973700039 797007926 935475633 154814333 822274485 326141555 249273185 721840068 762569883 595654454 959947140 921160835 344837915 499042039 901581293 476886479 402388460 11337494 890714940 856670176 291867943 327774629 906210589 221052438 362309171 699464465 264379884 649656618 167048838 157167424 438593036 869238071 947610244 477443133 944213597 292140625 13478146 86541997 314120194 202842872 968611446 142206328 699617736 879755748 518761611 611687073 243824419 746250228 751794732 800235443 163525024 351904923 37532313 923130291 305833695 800822145 45201370 543576251 811824931 895235775 240471966 550694116 785267095 948851566 32047…
Output: 5981457288

Example 2:

Input: 1357 287202836 979705911 666572572 724184255 368373487 675867740 892819781 309416217 175195230 515101371 420294186 666160336 56484608 635855404 50793234 300150415 34364900 601194029 743003992 753823902 488411113 340228676 545235672 572994895 439460579 294561601 282802539 486093168 167876231 787412847 5708545 393054045 958967869 706054376 343748482 351051253 391312735 929125354 524212052 349024958 43505084 733248969 301215817 708161121 502643661 897042496 891799138 814077237 264870172 491180154 948843999 638098115 54480723 741119392 990836514 517380379 576274610 675025065 906652709 760192719 147671674 576001083 705142168 396949544 433039215 504510219 413658710 204169540 929311703 989008563 141165309 122759177 15825364 64256950 579467996 951554322 816148044 272094012 273881897 319766724 4116…
Output: 6456965256

Example 3:

Input: 3017 401952662 340709588 984046324 108538042 137861826 965027989 333109020 579015695 305192526 45748354 389930788 424726765 948302538 805414199 950123225 745683626 205570917 991160196 797838666 849478645 229728039 423056803 675953631 956829867 646931954 91616077 134094681 205123400 251849527 243886476 87338623 903890768 558199413 686239594 46932867 307626984 119891449 80382413 462348417 750103780 631533489 602671238 425285189 525806864 361434048 928511686 640706637 776434692 468909755 243492494 601083658 359861459 184507035 196209839 109544343 388387376 39097153 750525600 564677664 590725316 117342220 160133460 463828451 941016320 256825200 503293288 959922653 94729555 161057180 662053005 625189216 274326540 248068161 794390520 774873253 936374821 905437563 750197903 449804779 600984879 17…
Output: 7451523072

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The ledgers at Skyharbor - MEDIUM Coding Problem | CodeTikki