CT61686

The Grand Facade of the Honeyed registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Nina runs the exchange at the otter slides of Sleekwater. Today the books show a list of registers, and the numbers must be worked out before sundown. 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: 2859 174841135 829906094 428796460 277499629 855699366 411599666 808063689 681237288 862596375 342186629 303132380 809547602 966591188 922391780 353761472 661349323 560474326 387171252 638955636 36161994 637726236 938629655 688499836 611897812 328486228 794920767 68712230 740185252 781021698 138984433 89194396 345849316 995622535 706433284 492505060 116957340 223531740 134858150 608200108 775251668 276847821 709588047 529546098 614723130 958116311 313730794 31226913 455185354 448575272 455448603 322007925 726090584 390321508 162735666 948810387 831341503 263234237 823326301 888731186 260633409 977861413 362448900 603240924 55230447 708325907 311319931 83637657 949873267 846093163 854047765 886293192 5526670 17425776 474590322 456736535 875233246 335531538 687479273 822653345 459822165 5573…
Output: 12345049375

Example 2:

Input: 2730 65310242 888512239 261484539 514250054 700582087 180981108 996164099 583556110 134130059 33823401 542446759 891290200 489551274 636887170 351254851 914390652 342729633 59740846 41694991 92768526 440095224 120727374 743763231 962577771 942919677 751268246 403273798 360920060 643159592 930878201 410369074 106512531 210681817 289464566 974511207 651564706 858604121 777529337 297170415 125953969 208245517 999905395 646000449 419951750 706777315 746709198 253317131 506911747 198953842 307986161 207478280 152720787 4368052 119905653 572618727 860296885 404341625 660299183 951909457 377087129 351249173 890047665 447501072 262983829 918015946 443420041 859206715 738351033 436404734 51908391 202645216 315014822 853014821 419660794 508582291 549407379 587863580 242904600 601820892 203306412 881…
Output: 7578402358

Example 3:

Input: 995 464965123 878073108 167200422 551518931 328030996 359268034 641933565 99240332 142633534 685481095 327242875 799080531 912278792 128761498 333409211 813016998 18544087 146717264 712673657 17693788 607606749 266161656 502375528 998386085 2898075 528505314 670759214 332922831 611724394 818515025 928142109 354152354 779758386 908837273 472081735 477253024 495811885 204609573 892058609 998772183 15886818 736632516 773011730 676239434 460398354 988485026 843994296 766359035 216042437 724886917 343526960 500923657 783558725 107891193 669113572 387335527 392735142 900968572 491427961 842699376 996502338 927790196 399198232 266638326 252466999 259355690 676355215 612784090 154730275 998725247 582461713 88141516 991678542 657214674 132424822 973635034 544996731 62819665 216012797 763784749 8755…
Output: 6150353196

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade of the Honeyed registers - MEDIUM Coding Problem | CodeTikki