CT62680

Vani's Grand Facade Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Vani runs the apiary at the fen lights of Will-o-Wisp. Today the books show a list of beacons, 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: 1693 688724570 392296651 226542213 826092894 307318925 242637370 933301850 224945828 438730665 651974948 195896450 443986241 241505623 138070394 878047299 595219256 773032068 194661042 709373887 967580368 298176437 389443814 337031110 714504698 25455763 344131524 956812282 133723599 708479471 715846182 710751518 657198633 89377818 866163461 550394566 746133200 221663771 491127582 532955524 957709839 356435499 892351424 677826816 625966111 852252920 164309103 939408116 320139877 608868300 477280443 680749654 365548472 649072424 551040891 299796184 937713138 569651452 537414859 246682319 731432026 422249971 272558984 498247441 431600053 846406547 800724076 82443973 90022956 895929831 113801287 659897035 414519060 265864088 256341349 665473812 569485457 467706984 574275975 418638426 656030876…
Output: 7563984286

Example 2:

Input: 2593 850680541 549430479 934301631 129792313 683011140 723065821 269212366 92327349 754977747 675003055 756617052 670095598 152927043 351352457 825654584 117234070 124797636 193771912 857171433 118537081 190862717 859216841 349848015 209445888 293934935 843223575 919283465 812998286 525955868 395720414 404294699 645766300 169233828 184573420 325876072 961168711 500881838 955103539 750622259 611590745 841060423 695323512 515092579 540870138 622668979 267308525 357806980 589637979 871869308 742794623 304417327 561484629 358210498 471279348 359074030 247977141 427686936 605635810 698189986 949456829 235491633 166571035 272285760 501809806 43527067 84614604 581165397 4238097 413815112 262295101 938993441 794597244 791075675 725163564 357654843 798684633 757161515 616661375 717298051 140300249 …
Output: 8363711706

Example 3:

Input: 1848 596124004 120670360 588325744 569249169 235267944 182982476 500720158 475022885 775099278 188915339 233376617 724274306 495210556 118006681 498061461 391186072 121363486 252562234 199864508 107577565 723093467 553798215 966654390 375890386 525423635 117337385 34731699 423005865 512859061 137394415 765265888 316953281 851328485 308438640 21071343 867901240 55499634 548778346 21272483 441652938 472184372 774815027 135799745 473692420 638348358 191577061 272732440 400030083 199716954 78857403 665914187 954372308 220052079 877190042 884696666 522934402 123887692 192552264 968969362 837577326 875587283 728738314 998565605 990517731 484660 354464777 416038377 272605387 785178920 906585436 241393371 763180682 524560007 205163969 981721238 8716370 164422542 413940681 375010657 568786203 54057…
Output: 7343315772

Constraints:

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

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