CT61286

Chavi's Faded Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Chavi found an old ledger of ledgers in the cellar attic at the zephyr cliffs of Galeholm. The margin notes pose a precise question. 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: 1905 44768795 728478540 576215318 360277231 177663845 808821581 294513442 541992242 836877883 804104406 512430388 356951224 706261674 953960510 500661262 638984552 430899467 49315792 909165477 914225703 709803856 167883351 91399746 757909209 253175425 863163084 157528664 62308481 932669542 658336328 806037139 801231625 342813586 994638480 64103807 953339151 414567589 111064113 160636280 393360400 166364262 162121599 832009491 632468121 554992983 865946046 704823841 441724840 993640448 58369566 822647390 767878878 46033733 669521960 381759913 352514002 126416137 407952046 104175342 980359649 854826275 448062963 882349781 880468835 603147597 114082325 74030121 412342322 272217432 307572205 712377388 570532824 685236237 553279834 715658870 83968818 940568227 535008669 22455801 434411012 11170…
Output: 8973431496

Example 2:

Input: 776 116680935 341029870 371748988 709949977 293556556 406743240 945550559 593881396 446586484 933472967 129609260 488220866 543016829 954126458 652413393 951652790 9876207 808726254 534529277 403190939 735633158 332644988 513803529 871074606 679597726 819829082 945633031 470640744 494481077 693889548 647577959 138173630 225099193 5572253 701380173 344733709 708386284 928587664 526571698 486808462 791615500 187131463 689538789 705307894 167214363 452613592 300435513 734977951 743213545 414334874 727486326 543645688 121212548 480564495 856299188 574758832 445560769 631185641 558231534 406785040 420016697 341911348 477821416 38404401 727407416 969168255 535371528 997024357 316831440 957210779 203945914 485684566 805076223 260405314 267477254 552001425 284062462 522249829 634172616 312630028 5…
Output: 6911760226

Example 3:

Input: 2810 964151934 63750785 814829783 287542652 285186035 596054034 312941724 685267440 349362565 607485914 840914130 641695267 843174651 919637307 479882943 955967848 721111672 876351052 236524515 64378866 406790537 280958151 938534555 45632861 479375893 12575946 570132787 423685384 854051598 482483035 862307240 868543775 180943308 589061113 950605037 232148802 442253582 687194739 526029138 238616102 616598658 542898496 704593891 573955519 934068660 806144117 153629831 295536611 462969745 485604054 576871092 356841031 336841390 518836155 64724076 78007907 916190088 346358773 770645665 912326193 341495355 192572366 924679083 481042247 934875259 757722975 196643753 589445219 820932231 871167391 97871723 45485403 996920851 896370988 806982121 494027659 146093691 878486925 440092639 353758128 585…
Output: 7909458304

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Chavi's Faded Ledger - MEDIUM Coding Problem | CodeTikki