CT62406

Forester's Silent signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the ivy courts of Vineward, Forester records each signals in a worn leather ledger. The guild wants answers, not guesses. 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: 1897 991838170 409615536 332940761 170655331 136014947 245235565 27464772 641751330 927797392 893314984 862478461 836398155 708603166 825077864 484704458 404743578 894073637 560530768 526486908 222843839 45147640 290028273 429712421 241357667 741527405 162964958 992099585 251512696 34561220 843690207 320310632 584573093 352538816 599371177 832766322 49430624 129954770 700333231 894986031 476913937 907762303 345681374 363015054 607219528 872654773 128514465 672418059 272216718 418026446 701887948 191384552 119324484 27360829 354929187 969308176 307835125 955702923 244605335 923710505 561538375 721261267 328897976 61319954 301814756 945851852 664492562 80483809 21467394 735377305 682727222 294200426 457679473 338779459 764349461 475903526 846757795 397615383 624688608 986055412 526550101 311…
Output: 7513510224

Example 2:

Input: 3119 614875318 146297208 177222392 447803950 947418948 972572577 899452443 59851642 29592545 507394827 398260413 574538385 184422280 700770805 159320526 546853685 602394259 979276564 451681725 746275495 447316490 911419317 830717782 122595474 394863391 125743674 259755319 713463529 26127728 963254200 771251860 586228120 434479709 912786161 618885965 483295800 664365332 757404447 857918172 521843018 973650783 66391305 791745243 96554637 971050831 298426040 722011500 309336814 100848467 592727941 594827985 925156434 944498648 516766975 307781261 266608126 752352477 174854748 214883429 56645445 534059628 668029134 109635815 464472187 873250043 637385444 196633944 773378125 994533803 525666689 187650249 668246981 448195478 844363290 534300512 510574824 618578614 968409004 130764877 817112251 1…
Output: 8045258480

Example 3:

Input: 3780 146195562 255298112 207899213 256903124 909467439 877706339 43577419 247543077 739072171 446730080 240605798 25627211 354617648 667023483 492843620 498795872 22936288 509310790 155550379 605112561 797262355 109306620 20884668 326554960 119587269 521986614 407190913 802228606 479629708 527606284 483698377 212335977 475505861 930327179 589516336 909616845 208078079 15260752 985047900 586929425 817545510 258615433 934501087 153873445 952899311 71307143 748361791 748845162 582714634 599149914 606142757 326819353 108218282 50598718 252044921 290236906 352553947 751106517 378540426 93294852 395293097 387930488 599848474 884229449 906593390 706002905 197770500 275462679 737279771 295337747 145962865 421814799 199304220 242372963 534514990 649698328 547000613 243026607 297878417 362788252 273…
Output: 7007891132

Constraints:

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

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