CT64190

The Gusthaven Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Sarla the cartographer watches over the windmill fields of Gusthaven's stores of beacons. A careful computation stands between order and chaos. 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: 1236 513782299 207811017 74499304 798800728 786651741 891891499 447717495 604776719 410093754 76827516 647762138 63590301 537165202 671426939 968834349 462519317 300477858 324021341 558329201 391066219 670703540 531329546 339718488 720544522 89186799 850954466 520768439 361448548 812837426 957448214 801318869 211239431 206954899 692579775 715910775 88345829 398056375 104679595 390960656 39093005 814959928 93157476 415160297 285172242 955093224 353591624 124975421 599150616 474938711 244484123 721741358 909541373 753209311 589294169 453927591 4480664 311942744 442242109 470031446 685900950 253739998 685839306 375716077 471562217 350060349 695708703 34689832 510670923 880074919 933742212 553826594 710757126 553956835 23023423 506999533 846646510 788178768 398551307 860516457 905623816 554974…
Output: 6496505041

Example 2:

Input: 3341 411244581 160277937 560957648 276591974 713255810 401559991 908950678 938682712 905380697 148850652 899781326 351591881 967305209 277006364 842352624 646970060 95211103 737725699 824067383 794883325 383749153 281552356 491016930 644648776 693822311 616539362 683718133 930532247 274497354 254475538 340255570 898231112 600494146 955765033 597587967 754619822 320230398 550443878 404299722 559212213 294950022 517439263 265745099 73544196 291349710 128333180 734811069 249716116 917349018 673540382 570202997 577285162 457959697 860881810 904312590 853430333 352590150 290425615 953518727 83300100 922137480 451822542 884847981 865194353 212003510 8852145 646878513 925941255 569495259 703833063 764061623 837640596 44587748 583134055 203276528 346227056 729161936 447260959 730849413 528497289 6…
Output: 11534504592

Example 3:

Input: 2742 585079319 329411911 453785390 587975684 913543886 968972249 956438729 692351963 181471398 807064170 11803077 160116163 87713988 723293276 51223145 135003879 226218545 189637830 671664590 552609870 654823227 157256680 640922210 222084823 766343769 148515935 332301433 148467905 664366182 150933721 572420051 52923893 122994760 309608078 903573076 817150287 839280000 481119684 85495050 944390150 651716730 862520450 845452903 947257986 931022852 726281843 518571731 974642622 360038735 455649716 873414073 335526857 791701306 448544331 787458762 250760506 378910063 326456099 993116062 648511803 32974166 212697313 164598025 907217300 958178183 176920082 652587465 442154677 507153938 958593707 659573911 415870098 84915566 242410758 773536093 334655281 633641066 268938563 681613138 27554279 540…
Output: 7816540175

Constraints:

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

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