CT60697

The Mossy Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the ember dunes of Ashfall as Quill unrolls the day's manifest of registers. 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: 1204 791836385 773584339 188712034 194087897 537703180 470152696 160827763 482377351 27555901 809437864 24911747 556025703 98280414 83712918 541922542 753643011 824808265 178575267 725578258 192574500 778105057 738890480 47693489 762286015 911102339 559339236 4699753 552024062 453545909 173530225 942142803 38249473 777437989 848146597 443068979 715719597 41538217 730972445 805590389 962149558 364850145 522359498 910226865 708594983 30666841 486843773 133544739 405276207 667151011 491581182 575200784 811886329 702948943 836244485 187198902 373869745 592294642 141642904 548077695 766584155 885485683 967829929 255710597 178564831 566741979 367398504 421217243 718335817 255168960 881509551 261151926 270971012 73999610 852856023 90997254 694394016 264164217 57666636 937368502 493768195 43713702…
Output: 6875338401

Example 2:

Input: 684 157232739 442206005 673275914 237917218 615358384 112205919 206365839 884479567 976445942 165301446 999838833 105526348 372710444 891613322 438562929 23244444 287277656 888539997 156668664 358142414 496757976 293371210 21601374 395724693 96540913 244016651 632514500 895810765 48643816 716894640 719883600 680997553 534427388 707444117 693515669 342281311 197532822 190099468 827842713 730227700 855733659 566080564 835262818 680785228 695739840 764374469 499089640 622822554 924349011 173819993 246777806 88476831 910922213 348616165 455721382 758801588 763159588 10002092 727204506 423086253 633885069 17559252 848486533 171169698 517161170 967772968 919711863 944657173 516764754 88291603 304162571 335485412 900173704 104757302 828150494 676862821 422561842 784145925 770091657 88666041 14060…
Output: 7741890197

Example 3:

Input: 1812 464805594 129380430 680819362 852263708 146377876 85333619 198356329 146376060 616036385 77386605 904919251 24680227 218253451 259092089 717899025 799004922 406288595 656461002 510415611 629089303 686594901 187083230 742547119 891031396 381332771 921521628 421401533 748037659 588362379 943438400 502004304 91596052 158129464 572005597 153160005 47463396 16803842 896071617 711119030 979178216 541765152 835810354 581811643 610605523 956783178 7229962 792395434 409157630 551985870 842852430 4365205 721098059 621874070 907384546 273242564 167143266 250507730 715704649 401110831 461131411 61124086 471314171 728637209 322273407 196041664 940163723 440882211 1222392 232316442 999331519 822726216 644462163 147765848 125256880 716063394 923741788 261632161 379590121 596717015 483217639 65160295…
Output: 7731215009

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.