CT65329

The Grand Facade of Rootwater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the mangrove channels of Rootwater, Cora the archivist keeps careful count of the registers. Catalog the new acquisitions, every figure matters. 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: 2473 699057445 644167694 389805517 341738842 23093562 488711322 106365462 829842960 914603957 74583793 646863849 344316157 444036698 641586730 350914003 769666553 277966954 785790189 336619787 540864177 638972014 194665566 181866849 442790482 796037792 543291397 211335646 470721371 816020852 667854133 47537243 654405248 714367836 515310532 577387974 853103392 824760508 738999935 456475091 439240944 961407841 40401734 488161112 919134797 669783877 916011009 741075424 384369555 287739942 790919405 169218518 414150275 516984353 780148916 652182247 725929373 609022721 513654578 647309051 399668725 179775345 332330622 510376634 438926657 992676716 487301187 948609449 800796806 951347488 398941185 381664624 461643753 99970216 262648778 678063710 544928567 66325004 63167383 932975596 630426134 20…
Output: 9117052281

Example 2:

Input: 3069 745194219 814849845 546155448 20790306 403821225 554293023 334714471 785990273 847111015 352215955 522323803 659593317 22563058 877710123 704149584 62601206 955709535 698546798 548508360 239286812 470492231 28808415 716816560 794141877 293030515 610467665 161552677 19568954 452151178 562643259 482547728 869850181 172571883 327037130 6114976 970534957 850561736 145847030 518560719 389937143 201076483 343951280 759382783 936169037 570194169 287868413 458040690 822407084 456229929 648248882 779858897 613481006 428802344 390202217 730541000 598016112 264988014 68928838 848781882 870860116 163689013 414104846 884843489 647547760 701160404 129672575 378465617 893587927 298655306 294864841 858779375 391210639 159215403 170629384 469772527 20925311 984216667 467957041 871888800 133322791 4391…
Output: 8431200492

Example 3:

Input: 2689 673026875 260930889 945006201 196718668 664537791 605350253 769006344 755570263 753765613 212320831 927596343 641150161 159432544 501417091 471959045 54733632 997509903 452356491 301169485 391012408 316941649 286309306 344237003 282698820 242572579 510414728 90997642 180344712 10918121 123515416 430505566 625171438 345862705 186026044 948053670 266628977 741066041 894633503 380166211 109096247 783186364 612089526 712854019 636698274 141622745 714249995 355859300 828536144 870149749 657615677 800691346 199124818 199926490 70632454 202186240 120547136 105936955 579613615 419193877 33508988 230746988 895357258 169694990 434764782 654923045 121555028 423923411 97157091 851625429 119067038 164319238 655788919 982126998 127381406 883451108 121298549 15341265 1890134 102902525 422298943 5056…
Output: 8924070288

Constraints:

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

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