CT62052

The Grand Facade Beneath Tangledeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the kelp forests of Tangledeep as Iker unrolls the day's manifest of marks. The tally will decide the next shipment. 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: 3110 550083946 715941638 297515153 977602653 403842725 570505738 240625121 339960991 672859194 418698034 923453488 519738435 905634741 704727653 115166265 891172607 479462827 220779353 329562285 138540227 111460793 827351348 311253841 480150472 68073014 727147230 527305746 455989119 990412674 398188400 222361350 646535596 861905081 173796591 46982418 104849559 919169905 220299867 117419495 992528081 958222108 73857102 957137238 803192284 623768647 9896097 231117226 502122614 375887474 280971741 111727476 378174501 525587522 421531132 740836475 767975606 382983865 388833966 818289251 144116873 659644515 966050892 189582213 197839610 917097206 230874919 664980308 374858836 500408373 160560602 229649021 517637855 858200076 157460589 36870104 203272962 572815139 803186897 683539080 100899416 7…
Output: 7244562500

Example 2:

Input: 3774 342904002 255808600 410738375 9773075 770481509 983853160 573139887 527498127 611886604 309713899 732651361 681421785 499972798 333093557 932874425 246998769 408494239 34832826 987825896 279557073 910887611 264410609 880397447 160733602 137878125 138287219 30920583 581376041 849407608 453591324 123505965 311732874 296529486 964586609 760890923 448721235 336130862 245826908 712336477 585149802 970349773 736037631 357171378 150547684 564136010 125607362 166840328 643517850 992325975 588358636 868510003 39147659 118425240 630517930 90540383 268726892 287032961 928204164 991448770 559840376 220062045 813907084 793164251 501782665 352257661 520161968 581153229 877581620 982119135 943347690 80579578 104281532 445879603 124853625 867214637 486954576 73347622 183397213 594870565 609394807 535…
Output: 8525045232

Example 3:

Input: 2849 41764498 603925070 227871720 551620379 918799672 223775449 158779382 71732291 599086848 766824450 742001845 338974792 420970030 163986002 786427434 669099874 202231255 632619996 454564067 959915683 274533206 659474774 824533146 432146606 865416670 137469323 462579351 855434025 503644618 917223103 980233721 199291772 484474895 932210807 597909104 914611304 757081829 760686067 676160359 958625101 263821155 213250628 761346048 800053986 210155035 785742998 707381925 46288434 656857846 576183830 599551155 514839664 534073827 529805065 550657510 234352312 835162951 476579967 823715012 499925152 418099905 383663237 482575392 13122443 145107205 136930673 356499471 666603113 647052937 842665397 336610811 881750220 395726385 332058018 652406047 279876760 998334494 978490676 854439561 729176100…
Output: 7676982352

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade Beneath Tangledeep - MEDIUM Coding Problem | CodeTikki