CT61192

The Grand Facade of the Starlit registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the windmill fields of Gusthaven as Elsa unrolls the day's manifest of registers. The tally will decide the next shipment. 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: 3335 180670368 749214908 383699568 909692750 97937124 711309123 666059266 210734869 545980280 198972769 328384868 324161093 46028807 880866713 281773837 190287309 781504214 287917667 717473114 644331191 167149887 462456170 924758243 561141767 288546290 277570602 76508475 471057772 609015874 484246323 810822408 410450253 738135860 790215279 310787211 965895647 3702906 986093330 589578363 809545076 642355680 357337597 209490914 326629154 233648317 132436618 135271830 902725645 450927436 983067425 911130594 596999226 222299441 332090744 949995321 49483834 645696279 101672404 926433114 171156919 952825525 943583583 186979097 55216727 31048848 929766795 927516865 143001918 397657837 292237675 738139304 627490474 381962387 705515745 919660387 397521674 694736193 265165882 701122614 216736369 171…
Output: 7762865585

Example 2:

Input: 497 975330497 929366331 540226408 699352921 769549969 692974621 166957380 304251663 217541487 419322020 434419081 506381385 443132044 51860393 621862816 9865111 170702181 942847954 410682389 435934298 690807101 847573525 88334322 236923006 833924716 768480990 988025711 602404931 566230470 211652416 260617698 890997402 940508990 79363650 970857536 964300867 655992691 819300606 802604162 591692369 868377238 807017547 607873663 910903329 954324208 309401226 638429718 155553500 731074117 283252105 475545367 258026255 975952614 108188808 406469557 464155906 947549505 411983978 400641681 235680792 108555191 289240295 469855482 150201022 827031937 612409267 627805554 472181030 848457530 18183513 674513703 577005082 395696124 29668531 907130970 677986904 819961289 990406321 241516993 148496368 662…
Output: 6508616059

Example 3:

Input: 3231 705873069 99409008 790663802 216349531 301845815 940477382 116100534 44851831 649136756 624091812 482488357 666456749 455622226 178020901 437545904 607924942 955810698 300035109 32800173 615992529 577425534 577901805 155669455 698833627 984721936 136255170 873865374 272083219 537563694 159827677 656294464 260977938 919799380 467542367 810012566 190764081 208481020 221482660 213281617 496950303 4264681 643677945 605953698 656681121 783128937 232179108 77724947 8609417 745210454 310899848 136166856 344093819 666128520 818041789 428869570 659278113 374324831 762827161 283186155 776349472 757086865 388338373 962021228 451814785 900172911 511817980 839542331 707418451 555935466 937929798 400235684 553049372 688419008 556639168 237793174 211548666 42587936 346465022 343836917 517440528 2935…
Output: 6513281565

Constraints:

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

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