CT62017

The Grand Facade of Marigold Row

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the saffron fields of Marigold Row; Bram weighs the day's ledgers manifests and starts the calculations. 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: 1894 220056672 536510917 656917130 838752597 841836492 120622335 250969583 601847744 298980020 81961821 24080867 436545494 626398211 417715168 398750827 890693396 931156475 976616874 460300985 851968853 118785393 482461040 343105897 309365555 179186838 394018583 717302756 471060066 530282737 476328271 754177307 792908800 415374676 982659443 729063290 896950402 9239972 481892303 904141372 172275313 744425203 358181173 601798672 475755242 367110470 317356763 821682290 316895235 676124728 923648158 310903017 381498588 463044761 429405855 322545301 541419228 817612473 964276856 995530377 968392422 618820884 20385423 863372563 772326000 368295550 368895779 536318870 575705020 590344823 968772096 545910002 858090173 607499856 930851253 258204465 580745171 970734967 19527682 896816403 560091626 8…
Output: 9802435986

Example 2:

Input: 2013 747501640 547844269 350987871 866960472 865478564 470884645 517966456 587270782 168381624 414904410 368939872 474083898 787053519 868704626 453322033 829866310 946475354 229073123 600190253 580283113 801818459 296730439 532867472 482567739 513405487 589706410 607967914 203195090 315449080 688154417 636093619 868296648 315949079 811990786 157388385 552925102 616275361 482518849 935812512 957874163 362245530 909936029 104335287 339899816 818951575 82734177 748967012 910263381 953424737 166325303 448269319 824261079 746500636 210103004 996386576 831073712 262864198 747064862 64721978 714742023 781119790 922077903 577217186 55574892 104896861 29828627 171655742 126400765 869112824 417715046 807078245 483282506 375605672 881521494 520832673 46840174 288283341 97347650 811548476 166213143 5…
Output: 8748914550

Example 3:

Input: 1478 65062911 572856596 766935593 728275487 944363926 403851060 737713290 464705111 334359762 646796395 178823344 910747585 87110903 505065622 304980507 146088922 77872115 943910731 218451522 221831570 599992177 445997639 63112627 505277085 626213411 38832467 446124007 453650642 313620719 913398222 86497331 972186416 434366402 199958388 656594710 761301951 217964418 383247601 392943308 822300226 993169281 3868071 207920452 177904192 323990704 303722191 392777025 327714477 57252727 866566695 519128240 722910025 545497589 31822084 934814367 158175479 664425661 597538213 282740648 350641473 114736154 244081186 122249259 909838240 899190647 346477679 220486462 297898159 810066 899088690 296590212 551376554 518339117 867782797 711404837 13003798 890105138 599509239 217029178 976596559 592012130…
Output: 11094263754

Constraints:

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

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