CT60291

The Umber Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the desert outpost of Sandspire, Emir the assayer keeps careful count of the signals. Plan the festival budget, every figure matters. 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: 3482 656822058 353742716 183184734 704621230 175351988 102238419 521148181 631152407 835636303 13943301 227564889 949058238 249271240 610328346 997637391 609215789 342450085 39795747 453033327 289975536 784128910 355085498 983687594 765962308 492935699 639139108 943768182 765266745 974741125 410311584 156764311 859387854 974996769 116567263 474428540 114212426 552896296 412370632 751949862 123173728 56764887 424369497 139456489 546779886 603896718 840136363 907607533 142364665 515054894 55426170 87821480 812419780 888060131 665251230 221945398 165359272 636357400 723330811 911837518 128019007 517798782 822641933 979642304 939543787 942248054 147696600 593990491 86514406 944531602 141821779 766023236 613671908 767668055 41317753 651143607 648260866 756823948 936908269 221808184 362446589 96…
Output: 8853523952

Example 2:

Input: 3478 820661307 274725695 330295203 607178260 721616489 421305730 640036758 606748867 382411920 86224899 143824925 455971612 207384625 691156045 920897613 482405623 576306015 785896102 594949657 104596177 36398419 861354744 112080889 273367546 728348751 842813287 705724491 881476372 548052366 403993764 359115488 666020240 614649105 81343156 194575371 196810051 500253005 211144125 888122120 444699699 126957461 728550845 504151236 833039063 10708444 313065522 69038745 170170681 851577160 622474157 91212138 410038589 423049408 511748616 136697283 391058030 694307416 283910562 438931817 158685783 853380977 618962276 733626357 788432093 572149705 46087825 700725354 301953375 800132154 551040084 650317230 387860315 125633953 873871999 360448191 250977787 15213197 934678624 227652520 305840525 864…
Output: 8984124270

Example 3:

Input: 2433 827749436 625992350 100959461 591219890 400907366 980439483 755444226 7607221 684222638 681291766 661030071 163823901 849772879 569858549 860880437 226161659 104237696 191877861 166531687 314769585 673094269 530837159 8796120 983943545 22537823 568276123 659666503 744274612 32652510 101733199 722540792 197759401 305400749 484269783 957052083 436058009 419323801 306234800 828538416 726060527 196707955 89656881 420357505 910272731 62121896 240405278 592974492 659369122 64000643 876472481 792743387 218493541 510440611 80719269 166513676 896264322 921092133 378665439 52062703 142375831 387764458 591891298 384305264 586584986 758739005 916995339 134200224 338816961 914541116 574595595 282282122 474848649 793450261 280565162 171667090 802612897 665092966 725110551 955136069 756187012 411265…
Output: 8606843889

Constraints:

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

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