CT62279

The Grand Facade of Caravanrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the dune sea of Caravanrest. Rhea spreads the beacons records across the table and picks up a sharp pencil. 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: 2560 19844302 893944945 839590897 117650223 919699790 458855480 163460290 611763813 35128744 234347242 561117950 812771938 358166366 789711262 755336174 101932049 287592483 495491834 14308784 713506657 192882120 487464987 291917985 832301845 925437212 390917188 42650863 797933499 749314799 417676158 612304459 150162252 869780955 395862739 776522863 671452246 243263595 188775102 221693905 767903337 611008748 81861118 65680869 896030469 198169499 159351048 253768660 869800450 471631393 838039434 678652050 32361283 986911890 429394512 888319441 459851169 343084007 396436351 326782211 835801521 710449207 777855062 582311843 160501358 792638002 775928134 737117308 99106196 878300861 312602154 704759441 869288037 192006501 269689066 869426756 628533994 618945756 504743888 819781023 540888748 682…
Output: 7629317566

Example 2:

Input: 1675 621411294 791661828 590865909 438407234 213308909 67083381 58036236 882065831 28501504 645800516 664998101 683501702 455938608 931205973 775810099 175464030 851890113 770398114 413850539 171486857 90559 58238883 548814012 877569301 773565378 615959633 969736967 348767847 17670239 827927413 144407756 465884392 200536325 727975039 421684463 900183243 738398525 567898379 188111506 68324153 170176349 838183701 429102519 26191566 238576403 737885483 983258054 104658597 511020816 679831760 67874347 859770496 464186291 498166547 290433558 209653462 575223525 123602007 463771545 795689226 486749108 731245077 991468524 566893107 449460778 39289498 951767033 769319074 387309568 742068788 393838946 278422809 626639922 543915645 999046503 733986869 428055131 934110383 408637294 12098749 486851662…
Output: 10965730286

Example 3:

Input: 1249 944627756 211097370 565896208 566147264 389158550 857114574 206607911 430401917 581079658 576827854 812466113 479117316 890252214 518662029 934756354 67335235 449786761 662949640 738288289 322962676 205103693 884999969 149723645 599162817 769082340 431000450 465600298 664043752 153200385 740118587 122771851 444480056 481930866 224931868 344217091 347011450 329476492 701749866 163285029 603452280 693795894 123796848 258420488 701163701 743770378 151756205 101658191 354814993 232521022 329769634 371256852 282118025 704391994 29726415 549203953 254751375 354915969 509627755 952567126 663766108 43035131 760794121 524430091 470000199 473183194 611946233 40905297 538265757 666976373 413437154 551293668 327631555 936186895 799468988 219334844 377788112 626227355 214646297 61686186 487916524 …
Output: 6483086610

Constraints:

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

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