CT63848

The Grand Facade of Alabast

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Quade runs the brewery at the ivory gates of Alabast. 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: 2464 482936820 309970365 566541111 872328344 79145705 59044508 67064800 431569926 197004249 423083070 665621085 774393509 831246012 554414117 816842217 562808506 505269758 944486447 299641604 493974388 33663309 930398104 299346078 691985463 931255154 259837020 775590119 877814977 805524032 30264511 55714818 885497316 567275015 73126790 343243644 903023387 35396070 230348009 754633673 697017564 808755995 793735366 617467190 566919305 704813080 822256310 24712892 734303744 59823656 311754850 798416912 738666410 518290000 813284354 370513872 566606605 262303110 64036898 385170473 657364430 674523184 154760143 484737816 720730489 535769501 550779191 487157592 832754411 660856953 230577109 119369976 590305620 40644655 796901517 957929415 230075210 22541476 679328637 691190605 552392429 29372324…
Output: 8711074378

Example 2:

Input: 2621 357309486 759915730 179692110 694111218 346021703 775135892 355474469 150811925 22635765 964491234 783210377 442287779 52905252 120088019 84556980 625167589 32035706 567692968 345655312 490419488 582890882 327845925 628388387 473411493 459006667 325310755 645611312 629051088 62411932 513009828 430554824 890910102 631214404 103089824 383489481 100024721 241191838 205448736 652050815 272478027 467409519 186523507 740760466 681085403 837459595 309409437 829023036 110167560 174038031 911100823 389581800 221368520 570189704 649755856 13155152 356861384 283461928 529338202 835244218 426581 137791097 518863047 793478749 821002359 883398560 252819959 314584351 883571342 930899206 487578526 341770566 310303782 218573672 812733353 237943652 296253117 990908911 284099667 92700284 818273083 77048…
Output: 6625510776

Example 3:

Input: 1760 683140199 398723675 822930626 965721689 533614154 879932078 700276622 646739820 211139083 547453396 842257467 352393842 577866687 751666939 499566898 291601548 69777462 122256499 599240833 730029596 601452812 535353694 975031195 939825908 284362352 908368136 299313399 607371792 907620272 344407494 229239685 137958069 730913209 609750751 957709761 792649322 825353728 339225164 940510275 418714705 509244020 660911479 982903246 475406134 883329491 943697381 954990464 267133962 810593261 984944143 917170301 829474350 206939839 349995060 434877920 78650679 152380203 35000150 861708532 728099611 472031019 38850841 798365941 784860020 427923963 888456665 616827196 814209255 565110819 631437536 497150608 358651812 542777100 862767019 158517662 566086898 338953334 449293666 690662056 892472993…
Output: 8262819720

Constraints:

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

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