CT65142

Ulrica's Ledger of signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the steppe camp of Horselord Plains opens only for a perfect tally of signals. Ulrica means to find out. 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: 577 468994002 789461103 382279318 858489839 909053105 614483290 310964831 839603679 66137422 911403724 447929978 775234558 363409933 599246609 341072912 22643288 457245845 56618885 273435164 970059704 441809135 973107309 789611131 355006569 196976984 856468846 185849453 879733374 486586211 796988046 357800636 448911111 31174590 813681956 844029740 923596846 377275143 846182359 515734443 513999284 10023360 997203286 709624519 976573904 52822169 268205632 837210298 61795138 620865335 742997630 895778755 264114640 567816852 405640239 205557025 560017279 212391725 982622995 775290812 104926661 696949807 462393123 60328045 750013210 331298586 448312614 572046482 560761341 663753763 719133980 64902376 129246811 34312124 655952733 457528580 607261273 623513585 363425754 244935732 59730749 7605364…
Output: 5609062932

Example 2:

Input: 41 780041831 95299221 956176201 969228614 380613896 373243422 47321834 2181880 148096034 125736241 937027253 471019485 379513712 605655115 506823100 524925628 623401214 545525088 474289694 105344611 882993893 611110478 461122091 326321717 184518344 637094292 596871076 554412638 202728639 394699042 967614734 142865055 620432043 881808211 575929931 853912456 859736364 506516702 254882415 136955773 403852409
Output: 3476372163

Example 3:

Input: 1977 961698287 835772830 669196322 381908871 575579522 803369952 197016827 579985733 143411312 66208291 7172463 73192822 405184985 983707956 192858051 150535921 681522366 249914064 788600186 355945312 926590852 601783115 23644638 423033654 782376735 344299238 560062301 614154696 17523034 856590118 922833182 922153272 550159679 434645760 170276242 406342213 201189003 771566024 283437469 433362044 701845540 227594410 452461763 689515274 990268660 41262717 135315959 235387663 644919776 450182083 78064195 261495563 45876410 636287469 400868803 355651530 819147934 487810525 39815961 515442513 45092944 674143386 111642181 754117769 821546306 482591378 917036102 932070301 570175901 920587980 767980516 493443320 218979583 563555945 341892084 855063548 680965312 85971940 509102961 31705315 80981019…
Output: 8034639062

Constraints:

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

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