CT58508

The Grand Facade Beneath Amberplain

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the savanna camp of Amberplain close for winter, Zaid must finish the beacons ledger - one figure at a time. 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: 3208 515561126 370631112 95743985 199281114 331946007 728629712 562872560 840905111 153766220 537980420 951371917 647968933 973130939 228069984 336691819 540753172 178716877 97182622 573481083 531670541 128916194 598228895 292661515 523523263 996854550 354271782 544314082 580682391 640999900 765698897 795286383 705639396 850167976 399877846 188961134 951421586 922182083 741418731 829413188 374267717 760722715 799796394 606391900 850868388 636356052 339170893 773869358 422454676 652295084 467182307 612663678 646026406 344587114 287066952 148484363 96406237 965180947 68916712 605369612 630742312 420801803 255191054 906504620 724954316 13912517 922264351 599809310 318436182 477748395 24703132 386964443 514213243 857965330 548974312 667205038 606527467 837086312 967111471 233279269 262808562 2…
Output: 8680874314

Example 2:

Input: 2311 850222382 417271250 96443387 896007402 981216106 974797078 940840712 346985285 562405219 244172839 930022226 720910940 1655212 803273544 398160904 849163232 988581025 890227129 229108770 129055705 174738735 269961036 287912936 412622530 724018526 843160800 590302236 346415052 150559866 241050042 341421585 87231362 862624422 666341200 807608908 906072796 605412338 521153704 818600831 314892442 310097508 988915588 948321994 233911521 751714503 464035704 608513109 329183768 127332011 832882595 580214919 62416991 296918319 691072251 544274819 961317478 229578240 446455575 178533342 619444943 967644029 712951525 152850733 658481151 686768204 729663640 314531587 80454292 38549873 446223596 580359233 501474033 408756993 158557175 879329681 216070909 588708646 908670408 298017270 84350138 868…
Output: 7850767660

Example 3:

Input: 65 403453977 502959835 814813084 424849946 877016102 394280256 756656277 446141800 259560398 818636556 497383238 351219565 663546215 175801748 457865907 823432138 94721944 27395971 605547989 747651469 87825348 550233082 6601426 981160159 804173142 280059513 417826737 544669972 658882192 851651061 568610297 171137830 755408312 240234496 983489907 169252962 290061522 666030994 273852410 313693025 929217367 97259453 13074660 603812397 52076885 755321463 971635855 187692881 832456053 251926041 344855517 691396045 42561332 835191879 606919714 468627416 894716756 711486376 322659916 339584362 630185813 590165437 785375304 818101856 689603793
Output: 3871918992

Constraints:

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

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