CT58310

Pearl registers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the smokehouses of Brineport opens only for a perfect tally of registers. Odin means to find out. 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: 3044 980154464 22842524 609285732 930666629 785549771 398010138 662208895 628029091 898285409 371371065 190514289 188980917 6673414 755866467 941615930 146891670 564343750 655684789 624462437 970052061 150770335 51362539 538874950 153442201 965251597 546344957 284799966 219399391 685503729 362523516 618364381 777368147 56157559 55180250 510135392 867980260 515352794 795470394 775348357 218707778 589384447 250745778 459366359 119018038 447685090 844891529 421224130 955106185 130398683 362556635 618141872 568868873 486299774 531101994 271076678 554329245 910663430 460599240 963107275 955943483 678755636 864981539 1639229 163089167 667668250 588180761 100337378 410141236 783888682 378432516 506495412 521333426 218523347 972708576 513657710 312352472 609166578 210063803 640029681 145975716 193…
Output: 8191820900

Example 2:

Input: 1529 301171656 469825046 653942494 753785103 144148043 156429153 900322829 196833537 270548732 350176494 531113342 738994840 795139785 364115031 264525158 233080885 161181226 795889878 29813537 676875545 923079276 543876115 510344604 964090604 966228486 942706112 117539173 977421258 428140891 865938256 562164253 774469061 138339200 856308581 531024555 263720115 229760750 747348260 940617877 986200600 280059916 411101479 794465289 92810532 139259096 774647319 101770496 651650782 573883367 992534542 825026256 188294483 767174912 855842227 552111669 316122813 56437228 730869643 551385071 971282982 341242510 314313126 446050304 570200626 444718592 163825571 597597192 114979989 955023394 800239190 851236763 379100574 965526771 240177841 658273589 204567552 938894442 206283949 957359696 93571749…
Output: 7118862525

Example 3:

Input: 3144 914473031 78185746 19907047 788848104 688518127 549325836 676480173 424268630 236147332 728844088 246248061 713055582 642786732 684506731 64536840 93463852 787444970 93595670 647493451 976334526 534916064 205257536 825568227 55634201 128238297 410479968 206949046 426487580 394288164 661968939 136278974 7593647 469155846 518103655 156440596 746497382 76406421 775312295 157151466 454706752 426016926 645724943 711690832 794854199 664172287 225660876 468474507 661400034 746692824 816934272 253446733 750537974 598729144 242315258 443121447 707861671 144898172 471601889 698215139 183321060 573077735 110142599 208811826 243511007 130347961 551849356 129938277 508290925 870280089 237584189 693638699 5439698 565729950 224135683 820410962 465127479 766871516 892235983 856390368 573759922 306230…
Output: 9228772080

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Pearl registers Grand Facade - MEDIUM Coding Problem | CodeTikki