CT60005

The Grand Facade of the Wayward beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the salmon ladder of Rushing Falls, Nila records each beacons 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: 214 314500349 733188204 810336116 350804096 694176374 826743729 312014774 149280147 793781658 556883006 455912695 4838833 917094534 272615103 732113493 523930081 81520337 481640967 13412757 137755209 940447254 660328123 466420194 902472187 41225595 819439110 471618452 792745445 709040892 622562643 662180283 727996234 761300401 973508535 729697268 477565899 7397571 508629966 700483419 643684754 17498682 182677508 233124231 956379586 1130055 366105557 584574801 325017699 25454889 995135521 796530591 396296160 342296182 243231477 867507674 994601602 774697827 740870633 775120100 988286029 75364244 896317294 684812877 291096363 452351109 857305499 313533482 393047709 391543022 403025478 33683929 14419650 781730260 799559807 597883100 222038605 1874595 194287 104866493 589463353 698665995 21956…
Output: 5187802972

Example 2:

Input: 1229 197651912 493157938 761633303 973568806 883464327 897580127 93371836 948784323 586803332 931805933 382110742 571060103 39480359 922621223 249496650 964297632 841778054 758730122 858729485 426805755 86880712 82560855 232097234 168713362 233329498 475638453 44030047 791818074 78538290 210288775 385825272 250427651 272429492 515215752 412056108 399253730 749785256 248708457 263791929 889264445 789794656 169590360 327991100 403911889 127118632 193502082 279450238 454488342 404561177 15554913 570828791 864973936 631364083 619040578 126277556 112130308 808638582 729506149 695738793 518258132 942602590 576648623 744160729 999423974 218730801 860690663 899054735 355010358 891937163 406904147 329090914 926221612 520354007 257156605 946633268 669922957 393512144 509408093 910254143 189744006 85…
Output: 8275662045

Example 3:

Input: 2179 552947721 706199868 592251759 773788436 33442037 966412116 804476287 278617380 728674559 774832208 783868944 438483338 849472113 771635969 217853875 347150972 430205542 169781693 269124468 664069036 181672373 528318077 982240308 284031777 387811543 635418826 678341447 572953797 870317654 477543928 940649546 489703715 800103489 108228191 560725694 801309025 490696099 210701810 509006112 649091855 471720280 209009421 115003862 311384051 212031135 750174909 948179636 836736643 408775785 852469326 347023992 3731424 448042952 818236670 67128735 342672802 852776932 293382198 641913248 309521423 803274338 271236013 679717318 462240712 782636414 417448094 433912611 843279381 285643201 973657057 692605914 339260056 201377979 302130469 974249286 558610126 620139794 295342304 31027958 133404958 …
Output: 6554244242

Constraints:

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

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