CT58709

The Grand Facade of the Smoky marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the island market of Coralcove. Gail spreads the marks records across the table and picks up a sharp pencil. 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: 3907 177223600 15656842 363233396 107225933 700800374 541276603 27320747 941710046 881433476 391390838 77844787 146445074 697132457 369164873 742384593 640009921 959962696 829983995 335410088 897705489 535700886 649552156 610060512 591453313 491784165 447729655 456618414 680994417 130522739 618843236 504646044 150373033 450489565 900061591 660171496 4141095 169322768 17165645 435689617 596311024 279239902 359096197 606144699 20444135 882343889 723286061 512415537 812865387 103060915 196083913 62261504 393605944 474997324 278895617 802546490 736876632 481571844 671413110 48324358 530718882 803942494 584372209 181969363 919190460 460588117 129710844 262792827 509071118 749756646 363113024 415175629 534566268 703002942 119786760 436645780 643951264 111811151 890602883 830143374 764873141 5147…
Output: 10320105796

Example 2:

Input: 1925 903916982 176856255 67911149 134003514 988859682 144673921 340401021 681150369 16055239 355271785 993509122 880093384 480614680 907102511 150307900 900980231 370565744 823657990 754698252 413488352 461930711 124293679 868194919 585306393 881431984 770251994 906270510 254921888 855740534 387080577 676478149 298389182 617754432 844580843 952124512 465993680 590457019 880705923 82931798 911400734 182189720 909179388 745982030 188309641 426300402 946667901 942678061 265173273 220845932 15679039 163654772 71589776 313999054 417161179 755315818 52586857 765306018 532188974 87305682 697306506 994655848 18006258 252361179 990355147 486323424 580611121 398738640 806949537 592004909 909708942 581734793 798392753 725316860 778692479 168676776 694412747 269284392 787252237 455880563 640393637 737…
Output: 7870641907

Example 3:

Input: 306 41608138 41686822 931190088 379319963 636780225 781597914 102121901 980763774 144098907 992152106 983857803 349266544 142341637 451506078 812440449 626896137 700316865 396590286 843060120 465316246 751057206 835923457 85596220 657510769 785214469 553284526 627279745 564671809 535668949 117157316 936044960 55417603 263731299 900445708 184985652 26366202 239667260 665507685 860218428 969262723 696423355 227767990 63558106 506573843 464783468 718094425 960668134 104761733 83492776 93262024 930072714 101506025 606006986 789266708 634941860 980452232 653735546 291758782 476324026 810935291 505798741 308664653 39568272 535943883 646612137 36700628 252014491 661831845 786694241 980555692 790785027 312005838 799021816 172988121 324506820 690165836 948009315 740261339 280900079 547304251 868927…
Output: 7301539250

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade of the Smoky marks - MEDIUM Coding Problem | CodeTikki