CT59909

Warden Counts the marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the boar woods of Tuskmore close for winter, Warden must finish the marks ledger - one figure at a time. 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: 1337 227491385 139330606 413192647 596651096 120576814 843914387 634544324 505486026 241309468 165597807 445918404 899266592 334114886 131851939 963261877 858993208 749958464 675054828 264322055 565330749 486030360 143661865 255229258 475414006 175851375 135515978 252630290 425975242 927857418 718147992 737365162 939617316 427540094 903319565 895649102 20096608 245284221 388615203 669239630 596793287 459268997 543471998 375291395 199827822 255546662 555782664 810705712 182702053 789627013 13455159 338083344 390528564 62212597 921638126 63042502 449082697 982839706 505393293 478837387 384316243 577474949 352889694 678093257 41612326 88919634 811635757 366095360 90415099 28834013 349682974 434156370 550351092 183054038 70001605 613435777 192029977 66623453 935317553 333399798 464624427 85795…
Output: 5273901342

Example 2:

Input: 1561 924344351 879604325 130166988 378043655 115869592 90793326 450180580 118767897 919091477 671472046 498346507 788216136 861715199 866462437 763949521 777020364 729188080 110868567 524209300 625528642 944490512 299153742 287964208 661587588 252037804 826444568 157522812 224507795 721897015 826942757 783888349 44100245 245733185 620806244 898012568 683193575 367471285 857663144 362737990 429776651 195942318 673411514 152604171 812607167 352097020 250832686 520164622 7236709 962023931 888343056 77454630 991041438 901113924 601207805 313354689 115897512 511530461 626261938 377445251 38289927 365164431 68863642 837046674 72538821 694565316 824410790 731708467 573036428 112122111 288999475 388708727 541555621 753996700 940500863 341463234 44360965 4144025 804598327 559769381 575484764 323935…
Output: 8745793290

Example 3:

Input: 538 877813678 613407223 197843609 126730762 672263331 908076990 260062820 942699110 809175878 61561869 680181567 860263974 870034267 589767943 871402755 657301256 987042033 564887439 568607883 671764876 399737893 661682097 160800785 487031900 881994848 72643040 387653579 692061791 601180313 388604365 834087607 217966369 546849812 623211188 95475441 193544241 591933155 40395864 738964661 471829488 123748532 600067877 595210481 701407764 450828631 73244608 849596099 8876202 306431808 160198472 253637322 973921682 29733428 363919059 42132988 532857177 897839047 865541012 952726361 518490294 832221682 895920084 215042688 913582076 344299271 731982501 65049531 801938557 329793339 293127484 878391030 157458068 622524454 908763876 894173699 744801592 621665294 70131759 676493198 842274158 6158118…
Output: 6686093832

Constraints:

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

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