CT65183

The Golden Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the galleon yard of Masthead. Seth 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: 2193 529063887 250441614 789042401 548420425 980225464 165304276 611799855 296523256 441251481 181503573 487847464 586515582 247695651 418706483 418859323 935439698 451450037 782412760 267574646 80911193 987290798 273945721 358367805 306322424 803392325 34820606 713083948 460752815 71975835 295467936 587901359 496337895 718556974 456539022 78720107 614840115 954598730 342898906 531457681 528506147 617360120 927488979 728875243 228625706 288784131 79826133 617038294 572538959 305548576 593753714 810877093 619779411 981623476 191493076 609528223 264232882 558448655 172398425 447863464 252479054 795641191 928375916 303203244 553808371 661130136 681707623 443108339 998569517 10800957 196948001 569096633 517105242 649341290 581072323 646490484 95355192 522932501 674901719 333203964 6514327 4233…
Output: 8037520430

Example 2:

Input: 2803 548883974 979881930 838600890 769512380 6048595 878754910 987635234 222291264 296239083 26602319 654765837 160937432 490988735 275369250 371297128 820081786 545541911 667237208 84015901 779738570 340418195 957531503 276018073 242890288 117146472 91212246 49475507 874240141 96241853 709540438 760738953 366103656 225316653 306113457 512449382 552599096 672044431 748764180 330503581 100691525 887177854 219637265 104360175 831570535 683800337 973843344 493938350 821449743 213493877 877896894 852385135 159873998 481665086 327043077 536052335 774150028 625843899 73303863 356460076 6808347 488482585 851332348 603823783 523535254 789710413 68482250 376398555 946277111 34447447 904501008 426535471 302838624 632734546 46657032 717555091 270353867 500394866 966469353 549383937 328187120 33633188…
Output: 9319512708

Example 3:

Input: 3634 598609233 973119589 603646039 269291492 341735621 359161658 963441298 337364680 466253582 475583895 409738019 849070645 870380362 88533281 235485676 898916225 308504152 676663205 543101241 135834735 840785236 27476125 809591765 401358793 135493868 351931578 241113119 479733926 788868312 297839436 739907712 610293514 904338084 82362759 842255098 758239943 536962396 739052241 909741918 393849360 761481152 343803796 346692837 462154723 825022144 200527103 328154260 25130020 62260835 126702404 562389287 890044127 72846496 820645551 84695423 263370229 829676583 424824314 695904753 25752387 751146168 830865763 276634368 440780808 837689494 626796618 577627781 904481850 932576810 247841668 32286937 764150291 464719103 611502852 467194593 224285286 710045256 69119808 710485734 556070755 76291…
Output: 10210691097

Constraints:

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

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