CT57640

The Grand Facade at Fungaldeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the mushroom groves of Fungaldeep opens only for a perfect tally of marks. Maya means to find out. 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: 16 648484656 547766645 71418784 364517459 591503429 451788669 51476479 539369080 746582721 38406109 202508567 178534753 847753130 539787295 275659739 31300816
Output: 1095533290

Example 2:

Input: 1366 66104431 349308696 904763041 986043365 954531476 342021079 796570215 367023698 636314350 195232720 856065647 340535886 930060901 957334792 893907126 393056625 700964251 460679639 268385299 720328414 750369702 9559530 319402789 839302995 17209689 514960124 498341850 309684898 21159560 886145598 670140890 259831286 802993036 383797192 333491929 311898431 308655603 395473376 879870095 696541501 591460334 969701741 951365182 785674479 230232853 851747709 701466339 239780129 585752764 798516264 463854871 504951590 869099236 681065258 643961390 243287039 542696697 921914526 181437134 822808407 154118668 110019343 813864905 584311031 180529170 287602933 474477173 912250232 481359925 461529215 977107619 149017512 834895268 489141206 37536514 871738531 158234320 25203699 728648879 141024689 82…
Output: 7837423356

Example 3:

Input: 3437 848351648 383141986 793761752 486960228 760796408 686747072 557116620 768586449 157735181 741348907 790170486 805971754 127412879 612289607 595227719 270392234 989750723 232260929 674013431 743804364 619087291 677659652 688659133 481818924 417108368 505576661 365671419 630505630 245711866 960585185 672652930 326973894 38477238 231109178 217926031 715558335 767670646 10153771 867368236 303655252 472216964 288445135 593922110 640539726 311454903 920661864 206943571 463254734 415220779 621869818 455661136 313259096 476891189 53816949 348913902 307927349 400171051 247375719 273052150 88688752 954174213 915911428 116375269 467968859 498196662 897341646 546227369 144488971 253309223 437851298 962811054 82010238 990961964 801074132 924220098 906554350 683140212 666440625 643675518 198068946 …
Output: 7375495299

Constraints:

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

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