CT60335

The Grand Facade at Pearldeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Xavi found an old ledger of beacons in the kiln attic at the coral atoll of Pearldeep. The margin notes pose a precise question. 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: 2440 43365735 203839914 99365161 431598607 315929245 268670876 946434597 500755812 791419129 751533393 297858698 163769487 426065954 264530437 972274823 283864401 817165540 444610379 478952309 539864336 830680706 790485514 360764935 783219064 421292273 450785730 543944781 514707230 153386979 676182407 999988372 135117078 273369934 725733594 361961574 370101600 255365382 965611435 480476157 484149312 110497948 837185671 615790790 156599125 712626627 539559188 622127591 900261857 328815572 898817947 183112231 62213188 477408731 702847663 632830487 606841517 625802492 265338270 445208771 100082945 686390348 472898521 216548845 887264010 842481007 651018208 279585246 237193168 133394814 321409696 453721170 261061475 933866383 961538128 538535467 736463100 603475743 463809412 863635628 39430059…
Output: 8090240616

Example 2:

Input: 1480 262987308 89844494 778890873 177455105 931299359 455370287 472515482 151563004 726967136 302957086 191431779 330297644 118857533 243151594 128505344 287590477 290465419 575445505 485667324 956156177 338614687 969979652 475023802 228012726 888991905 95756276 962721837 291115023 387925395 12773732 688638198 505649444 843462349 127455328 845987327 389166695 100408942 441265124 997278015 500202502 50913716 824340326 654149012 786801860 156580068 939294222 92236228 31934074 363207325 429053550 33350619 84222866 717902828 298162021 382858975 353788029 281527072 586688427 503663164 819900483 772511602 841309392 689497068 634665345 676379746 966200619 237437613 967568131 46968427 671509959 912340197 455252974 131133009 264834164 584536891 325315974 399327216 440668630 583299671 664167925 2037…
Output: 8772491808

Example 3:

Input: 2216 788541594 820804243 269439114 627274341 884194125 439013392 72913154 381460058 139153139 662929576 487606745 847261613 258056738 689446746 932517667 404439713 104802982 393797816 133842343 246532844 320513853 732312244 819047325 175514237 59263341 945000306 40098907 649581412 6600486 161362332 534262621 779553388 618552356 424506841 118060254 879022589 453145708 327280795 702417235 898714395 877987433 202045892 551691782 386686186 210308626 873447367 641478461 163255086 355132515 561835404 351110781 647593519 665449698 492271854 405122499 879265472 20787048 414875125 324193186 832348637 449057219 828778968 299497766 574161413 371791588 564996994 656793453 980799268 517135775 309193324 243092230 694944746 555389068 25279771 166051983 835030310 629838728 375190455 130524962 903638492 40…
Output: 9771427524

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade at Pearldeep - MEDIUM Coding Problem | CodeTikki