CT63097

The Grand Facade of the Secret ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petra runs the boathouse at the salt flats of Palemere. Today the books show a list of ledgers, 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: 534 129827605 969749725 734970826 641488704 991540949 961247917 547524459 14514189 616434002 492454669 824286691 645579417 271800092 215083376 333156122 789487050 721108384 317490996 165557467 579868330 153973824 707862443 685445911 394426331 465153794 109599897 854544170 62458968 863155613 546240819 323160151 924294515 165493297 918661997 373033792 16088264 599582958 140413320 156096092 708456904 594688246 148890591 577203784 834818084 445795209 590748979 432301687 279423844 677591847 401175773 563521239 333979720 788658833 929982073 90277940 640715418 103648545 617123611 667560267 609403605 646205677 992551425 508778038 808106492 866272561 37950751 635912797 263317358 120322748 273681309 628898640 706468535 91742435 672707436 226500321 342474291 205880538 390471727 854698012 996741134 97…
Output: 5947890480

Example 2:

Input: 3925 232922797 270613065 762522397 718429606 598223212 53397184 17281838 856989898 336291938 935316986 538768408 75227509 89384078 463333031 613734272 723396858 922317392 767794791 9756062 306863868 112865444 965841447 49643068 866288930 712866759 448612220 437548165 92919339 196817752 749171021 373614932 960908452 365722683 109472860 617777569 723739396 412984016 898824065 816785734 723529212 664699234 323098228 258662649 709793075 173854268 381396104 626787441 958672943 343659207 737563477 325188427 236068600 417796739 735798916 548788199 598509401 156307851 868407336 923307491 351531358 144034237 144348023 120165887 988526963 855580368 742421148 456262392 426426078 704678281 179091428 128959840 971941626 332170714 739390166 708550774 856833293 422416368 428547981 147930855 645514416 645…
Output: 9199014561

Example 3:

Input: 3115 426022015 229626437 848539791 826662158 988755288 533240618 682376238 353163376 523837312 118867782 595724580 884891196 569010971 565130812 166803412 764185159 33915420 942602563 794297892 101683503 182355913 89203088 712610357 11374678 971692827 803014880 331133611 277006833 820213715 198583238 533353259 239743241 752216854 438153304 555539631 39126790 209520399 198272198 215646523 23835299 474015284 821639719 814362410 423331272 206840013 415487178 535322568 952729241 411955690 382532047 296396074 578462482 696733928 286955545 17468391 927696013 594646758 511216307 814625928 560178338 470581183 921652000 456377436 53378195 219207872 336702601 459965556 401604091 571398911 838000058 874352088 878927121 467929171 145589103 419975232 719286462 944038461 298483917 182094870 997561290 28…
Output: 9236844693

Constraints:

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

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