CT64737

Orin and the Sable marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Orin found an old ledger of marks in the cellar attic at the caldera rim of Firewatch. The margin notes pose a precise question. 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: 3537 559913955 262913397 671526375 43993442 610624844 7859250 121982771 615549378 838082460 696274388 184115968 176697683 671048280 320865546 178271325 177932791 202699454 505791365 42477796 825023735 469288663 162364136 460088571 496183848 185226414 767682105 96848245 751556148 56504812 414674770 568788366 26403742 416973255 860992744 93548774 99026566 586006483 341619918 646041602 790485555 250412036 882408903 257767185 828474535 895464223 718662443 185076465 347382317 671533316 767031499 239025783 703389084 25063238 80305890 9466916 193655930 295672883 995093867 660957333 431912667 930359952 407762055 717799095 958407454 426640899 184531030 633220172 973038040 179086046 74212778 843659037 714333799 681543923 128274000 516306112 175288351 816884644 116047367 54248881 998101626 342134019 …
Output: 9481249044

Example 2:

Input: 1499 257329011 663190101 908543716 607228223 133825426 16704107 515136130 934912701 654534912 912120273 702129311 925552843 767359737 571954173 376501083 610402864 630576107 169676003 987763332 896803494 48026430 815943214 336480293 761850416 765424191 327482511 845387409 195606360 621989155 546928044 510337049 989065112 553796858 597422458 906603241 120107656 702871179 390370071 490519329 707483172 650569012 652560596 876434701 761470240 776836932 916833900 983048721 428218425 588374040 143838531 960440730 93591027 737308395 525760311 98809973 797980460 556271156 543587326 203718383 480332362 312704083 755066221 230509684 691064057 867757077 967179455 820879532 861060717 598848394 410591526 400832875 59646600 969142595 778555139 476242788 330361573 344143055 286704974 74365 924890138 2200…
Output: 10593757350

Example 3:

Input: 2189 8312324 98592428 191903550 876871754 285597236 926246013 598400680 215815355 363637245 494615314 377654578 359395689 803592667 592763994 593288131 136829161 383810057 771844560 632235771 346067832 695402486 627528989 827988258 724917682 770065537 256984984 836439838 415753700 417650122 622817064 490920724 964381748 398300455 846616864 54569354 563159698 200353953 964361822 676411282 921567665 368852665 773020786 678805653 732580652 580860846 715904986 406075826 792882642 378515400 584981564 401520161 273048281 451802430 364122960 824252726 932190350 709689243 240559825 996117466 366368619 410975825 724857154 328481388 536423046 810442695 648788792 882451361 529299171 575163203 71337692 947454056 811973917 343118761 24701918 767992305 209297896 953085896 923866797 829814968 620641695 8…
Output: 7697914400

Constraints:

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

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