CT62210

The registers at Petalbrook

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Smith runs the kitchen at the garden city of Petalbrook. Today the books show a list of registers, and the numbers must be worked out before sundown. 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: 2173 287309231 313368185 248103267 895793342 535855087 167706295 135736656 57050298 274991443 865277865 632198069 52769715 969547843 552447513 53778331 15147375 121873684 176041704 56680935 980569708 967917247 473903326 734832002 791287640 197816093 634231562 985000431 747666085 389711885 578963789 523053254 268551301 974031313 891132187 526161072 513742265 771100561 490913013 693923739 403759126 856927836 411398474 183967720 612900088 973052973 242263099 251690985 800178953 144053577 513234461 596431268 955660002 734440947 794630693 603739519 183343824 257159681 418460180 849026780 451962551 88068460 2277240 901082229 685444889 863588467 742018179 81862849 576382855 631310813 437499159 687191319 235970582 562926387 18290158 25525852 628323427 972540081 872269150 660175915 72631884 1535386…
Output: 6483011906

Example 2:

Input: 850 256340268 547037106 623699730 626446254 790130359 48071438 155268414 794325984 870075928 671331813 817426636 685346275 230152842 270868039 754696635 271135901 50009014 395644443 997760649 86226933 131755864 430993018 519004270 533707632 832862448 422395067 662600275 788035125 616143305 204833094 769028487 501907304 767779584 518810420 456812626 843054206 28684733 399222143 456486356 319685047 133615370 851984659 173504107 803756862 346627394 415448287 752238786 896302678 254919188 834975434 547437 497461615 952011226 618809348 580056662 742329890 286368433 233944098 864470797 829300438 432161799 257497030 608952394 299680471 215077672 437617644 459517392 360413143 611268651 137051774 389144861 5772353 20209249 758245703 696900231 501534545 963761548 415641129 41560507 303434661 5230017…
Output: 5422253922

Example 3:

Input: 1066 865831098 79633858 382530583 632434169 255048470 514698356 416691432 664541390 169873758 340466051 345114596 199352775 550770207 412159621 25193634 93514867 191936270 86971035 995030998 877059752 589569701 851392008 203961417 397485087 807225356 389453314 746007162 325198363 210208552 230513914 541940397 444228242 113950056 329333074 191400437 26287816 230104866 253088794 904166208 81680777 801020654 529189818 800836657 293052246 79213559 192520227 842671832 963785177 388248381 302909864 825826629 233793438 286124206 649834795 483734061 977744289 28928505 568593867 277013203 629853305 732342453 577294028 138154422 201178834 989531661 157130796 107346423 712698895 395258113 597514425 318410890 468525051 487262019 229994174 449958584 972870649 957737559 661524952 209962899 316078077 469…
Output: 10197910185

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The registers at Petalbrook - MEDIUM Coding Problem | CodeTikki