CT59468

The Caramel Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the ember mines of Cindercrag, someone must plan the beacon maintenance rota. This year the task falls to Wamika, armed only with the marks register. 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: 814 349866920 45381670 754930360 420133399 786240291 746478777 500628198 629362327 219035972 517459751 906337280 869175040 51011434 974858412 189663875 351692903 776512470 417966496 60063865 332735277 93630569 699777304 421002540 866977715 548056147 356713702 902064885 50117272 410417492 307746559 556314512 361076576 304433706 728583651 923650930 775197252 415357869 15569603 823449965 120576521 59257265 795569891 74866193 136236673 387924134 655305168 731086786 795228742 464121792 445458667 361091117 513643490 979322454 252463868 521475070 463338361 540228547 599344115 918894003 350550112 410680032 88765167 29129373 491084759 973732898 638948381 819433521 914106654 12675275 21355455 10908560 16914596 32990546 159821308 210859006 957986457 606847835 768063440 806243303 418154755 790835357 2…
Output: 7340238642

Example 2:

Input: 1066 36859399 381165400 983169057 395281994 188722632 676151968 101726335 804260669 97568578 187481818 849159411 490013945 418366623 446079138 52518415 506687948 345143459 549913348 418301161 168383589 124708783 372080364 1459919 922206145 769604167 265568422 190580123 930644914 641183328 281383946 838609774 543320188 467981708 916992934 887251482 877161823 575668293 78418117 165811185 951193889 693237776 384117791 807576073 903661542 212012069 908585931 94150771 127969563 797493721 130711771 916235992 346478421 178994363 141016400 989496947 989308569 607627104 861240889 354183115 289134130 571476356 600777021 477311643 283119607 62450842 180139952 857961660 444304137 893340928 767703580 227831957 190018262 321999233 730723646 128035905 374203894 985253730 115348584 494886768 542914341 612…
Output: 7506982857

Example 3:

Input: 1800 684455376 107325598 478077630 598762048 486555355 555080241 772578810 983535459 861736041 208872819 82155401 955136053 30672914 314427853 373519399 889338658 468310122 845207992 346005122 909821481 698859977 439170821 201293613 506059811 884198973 384644177 71916417 341538759 992293835 461537716 410732573 61879269 820813867 490588889 157853335 765399926 636267530 340301399 702550793 751744102 517318134 133438354 139095953 964638645 939974381 855724677 616412042 462666561 821851744 269453927 798159019 906373933 185775178 592452448 419190272 657942133 468768832 149537788 978840782 183580033 318446237 260360774 487771164 291843194 369212815 116711379 76360377 685606899 236592695 719882046 882765852 904577891 759241015 309619144 250305620 151533250 795726713 938939237 245267509 670847018 …
Output: 6874426986

Constraints:

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

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