CT57484

The Grand Facade at Starfall

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The log keeper Shepherd has been asked to file the annual report. On the desk lies a long table of ledgers readings. 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: 1929 725683762 310439986 703125875 579040983 472157998 142126266 821639782 47680713 542742778 939185676 410448396 367713129 905788913 495572809 457442686 60009751 185192584 114746201 869438809 185150085 799414168 295990179 269584911 129217950 20514119 128710620 421216105 610830097 759219877 73834930 155963854 917872353 158005506 77493370 957851214 650637299 409625495 287033910 504070092 722214142 198450442 170114729 228171707 416155743 525063251 102686343 346910911 500908123 755275049 52542821 842354431 607168689 316009710 212303885 86808558 226340990 829304104 991997414 601545429 755559514 227739193 174139912 253865712 894305956 279345661 250005665 652898785 978151622 726302015 144443967 751123353 748386332 904200274 730666348 320607587 19182687 242781139 862630204 658080308 296146883 842…
Output: 8809574175

Example 2:

Input: 2506 378873542 573955382 542350850 817792414 952843655 965541657 917560105 199173287 593612291 631168433 797416595 148208748 615953811 455212526 157883877 856420588 409839906 765805361 127994492 205225535 379600250 987223503 536151690 338765407 791824162 725347316 195330055 346029473 158037134 617182731 285040186 169955471 241412420 880017659 567360873 626986112 667706827 237025727 687463260 864135064 235913730 454812801 229195627 22214798 432495505 144194834 825480859 197372361 333010914 479215905 743589719 582260218 117647826 972680911 696152389 215892329 516028915 582790705 229336765 731310869 881241382 437061773 986426029 126748819 878266033 611424741 739258700 652615583 726693526 84913623 705449568 68884572 571765450 131884961 553647422 595287616 492248665 578293709 148555393 22140881…
Output: 7256867266

Example 3:

Input: 2570 56344838 455838124 265579735 502474256 51559209 89769468 657457792 127302887 826945500 913225908 548187028 340158673 651843609 294330966 572280536 884605818 615141949 928721303 336211344 806406416 601209488 654835626 909395758 787785996 857170295 402645994 829169916 858909411 367987027 300696018 293393969 146220199 749524471 467878782 936176278 43508118 93396112 357858109 473098777 261176097 967171108 491969761 320988354 900178479 201616121 857717608 580382551 223278896 469969569 767219483 97717103 576089058 477789172 726486352 180986339 634793688 992074598 222740442 896325916 195307435 415300753 30841468 8176268 869867948 973303608 174437373 856443996 953348405 844284593 537296051 583192506 697023821 705661082 870091354 380538638 493685067 284399530 779792104 162121172 582378688 2577…
Output: 8101789032

Constraints:

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

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