CT60656

Mossy beacons Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the willow walks of Reedmarsh opens only for a perfect tally of beacons. Elsa 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: 3913 803207328 239262037 441155124 606459146 371542546 834066245 619686038 623445265 167138206 825533669 294035093 557874442 961194201 169406795 202591508 823531954 591634637 514597207 759039759 275671571 947840552 350795135 622889181 781622286 946184276 979454797 256407610 391147199 104505430 5638333 891131191 191159919 383471297 887731369 20005390 98806370 962587426 398456086 536590963 702299832 824099390 204282263 377483117 62600565 253405428 467863752 973675489 641458970 23142715 82829480 816671817 95151182 518913165 806983003 30556569 582683103 790402599 240279544 526890868 148607204 244296828 254459782 692385592 387311336 750299901 807522483 338262534 92883580 306800017 744860428 759309132 84724259 467317081 219973624 604778981 472741909 168020020 124803822 678193831 244760153 653482…
Output: 8416344039

Example 2:

Input: 1065 145321655 205026598 798696805 190670756 70002808 677251986 436247295 314600480 600931033 406163163 583122165 993793217 164571712 267228805 350038605 285595556 545792089 379643361 410759281 766848756 705509513 10606856 757329869 867642756 271696816 727934199 512133068 310266744 907578506 338281540 375887057 974473357 991783385 237879734 674864251 800217168 287641231 670568319 335531630 955580201 161435463 236454524 109004263 667941784 873423231 191004215 643804856 460042607 529649519 178418970 876981070 888918732 782531962 679864551 623989656 361694764 559242777 294122719 844657061 560668701 150309243 396408122 860994042 12198630 93482431 165760430 356817219 935525898 21115841 591127701 247053643 113379459 716025927 652470692 260500316 998985167 479753429 522906217 364086090 756229895 …
Output: 7895286410

Example 3:

Input: 3740 803349052 5983930 5801987 138136878 525210258 138295693 104802751 351955156 92250184 169314540 45567360 631719147 602721508 957338378 921234596 464957400 85555292 843735755 512234177 550892458 304360613 831784650 698668122 783574903 279394588 833101538 567650695 222155071 343413497 189142983 642474396 248494367 348195832 869330098 611477937 288219606 234955008 185024594 187322052 233077002 212164663 96192145 626804225 891907694 688539468 922961792 968813525 793306241 314711515 451990308 901378316 523049941 532596211 32848938 577996966 34527205 889199647 166808374 58922270 18107287 201719094 444070220 599010456 436856592 24947350 728612929 849678977 791883464 432222738 838764167 659438790 179669447 103756850 693403353 163305775 231517438 115707429 829499510 559219502 720977591 23323505…
Output: 7012610964

Constraints:

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

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