CT64648

The Dusky beacons of Rosa

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Rosa inherited the loom house at the ember mines of Cindercrag along with its curious bookkeeping system for beacons. Time to make sense of it. 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: 2225 647312479 252400951 470541374 735413659 878592221 622703084 349749450 585005100 919757972 338322302 610127355 759504018 612666766 634246679 222487043 386945189 699604371 851095754 466465060 208786704 468737029 884826123 399473435 134239184 178435933 468715058 639383706 876295756 744203872 894735634 965616738 708506264 836789149 884438183 84913492 966700638 421617201 783791618 760174894 655654894 661286726 214197657 193819389 285221512 510571445 553233749 346133274 447185615 594859281 136448017 625512287 309392463 26196185 924574066 393975668 741837828 146653621 297891195 757057825 336367883 696221412 366811089 326440024 401690757 571771327 778476975 557603632 591342521 410825624 163215967 180565094 661752160 667447677 236004777 574176027 819047420 970700384 999756031 578726615 8895396…
Output: 7817923440

Example 2:

Input: 2901 494315780 429067607 112003640 38681376 65778108 113455558 691284310 924473407 835778135 39390700 918198531 137881418 137687639 143292812 718223826 85367506 660553758 580290800 705060321 724318942 465185529 635169916 33975775 144517049 724278347 335195003 163167926 214429268 178350214 460485917 518533718 136220505 5948358 188177279 153461008 641188753 642039064 561505190 175550861 674715510 178274262 511364622 684187702 154062198 979225377 169356720 826694029 806110897 447406240 321646734 257750658 513274816 982428822 379586726 268215804 796306171 40697044 868940505 565441703 127983613 418730309 491260746 111768570 922462098 131702969 8560239 950715968 444921396 550544168 841029964 340682096 196796797 619696570 965107825 894165581 611371195 273126329 741804609 780764141 416000944 83026…
Output: 8793350146

Example 3:

Input: 3974 686150400 849335221 443422111 339204443 275659481 221882977 160660164 12606075 982308128 121661611 23795108 109345128 699347038 280060063 707959246 489560739 600229930 683597623 939757610 868308409 319342585 827717519 407409044 64521986 863153497 764962822 58970011 42613625 763591965 351121585 948944071 559437597 33866913 587433375 717350639 489916716 489748662 384138964 669366498 536644671 171834180 948692450 460239634 789865900 709905511 172069218 581628321 164760552 687131883 878787094 33224071 852006706 319459733 949445438 338304857 300360290 724614290 679625586 137409558 81432147 330273573 535941349 368394792 98043377 860880221 553974904 748441413 805542104 94245510 485380441 296200325 164076363 851023144 631108869 152898850 104097777 667623309 657810704 228774785 645888945 15968…
Output: 11394055140

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Dusky beacons of Rosa - MEDIUM Coding Problem | CodeTikki