CT64558

Last ledgers of Piper

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The factor Piper has been asked to decode the foreman's shorthand notes. On the desk lies a long table of ledgers readings. 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: 328 385375292 548035973 766631085 197994973 632994141 928403117 919401149 217815458 51689325 668201564 586577578 358753025 698789351 166806729 395303110 616436320 605755782 797254175 538872056 872340825 159325613 324792500 426765027 270611725 587468310 339842027 729103332 570062649 317057856 968350095 236598399 663496105 205952123 756191101 981748039 718535950 46887911 871830233 407310961 328289246 250943290 244263306 935744843 178369559 948135781 515481142 613805395 377179289 714694034 293592810 511040199 959048156 956474248 898632850 989325404 115937980 650027554 629185952 14740610 417776399 994909456 85201078 876109948 550337079 769346924 27236393 278002431 108248805 958160829 351289326 369260697 695211005 296720749 663102244 811741350 878986821 699183353 598330601 348284466 177357466 8…
Output: 5336742240

Example 2:

Input: 3012 460974363 244657128 209200156 196372386 313590180 781228897 490097295 480865907 510057263 69280377 381830634 578391600 843782463 939930682 379696429 493590342 527975596 785944597 354311283 969170888 118612257 370706383 513842509 413475464 766615018 58557101 786914651 589237526 598705626 402181723 922530646 814078358 667216280 715789775 668274701 809785554 311976797 849642859 864611095 662515345 812901210 445182087 900545071 611219442 90065789 838023362 468164926 825042333 140952058 396999499 399295592 140861184 182696140 559198626 616840206 18478103 309149072 473780663 437106574 475600867 142061198 121483761 541451477 295745493 506316936 6120177 125354931 78703373 830246006 164090576 74716392 442462875 797912575 898615330 530213417 693409429 419530373 345560880 3415244 408489713 36639…
Output: 7872673176

Example 3:

Input: 821 962380378 553099862 825569360 18691327 287505852 795932936 746328900 240018825 170325606 779239541 60392841 391305077 759292225 941995206 247336746 644110976 389019806 95896228 653919344 262472415 880888128 247683627 914081311 965248791 343485415 652551117 513363889 749150212 199291041 563535395 206934865 259605000 475938869 186973625 536113918 553242709 149308331 949333914 4924201 959974036 193380796 728123734 210661910 255765091 282412057 57112580 135160963 195154510 550074072 857369612 309883428 721393483 551515992 750487119 83150598 369588798 205931252 157630008 750909775 629844949 23502581 222639057 160563254 91480379 200523085 487328244 813020273 253022676 794735746 637253882 467737553 278722003 687195420 635046821 457347351 641365259 309958035 605737259 905956374 331180974 96991…
Output: 6864311900

Constraints:

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

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