CT60210

Lazy registers Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the obsidian flows of Blackglass opens only for a perfect tally of registers. Trader 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: 1222 673174471 259304736 671863966 161912015 101111451 714534645 504580716 562223970 899883704 616906184 568995892 584952291 901351671 296125087 995525624 291317785 941744558 474810363 658418425 529065700 58011275 993250216 476482034 91753820 854213590 684381877 137716937 942055677 853819622 820176483 960875450 991614895 651468762 753829809 955757829 974529013 883144948 158581027 345015514 980191764 183577774 111174691 398480937 992317771 249492460 527630438 558111274 399893927 542246631 609760899 590216560 857260650 334348521 901637638 304010574 625143644 298309475 647476270 34427333 930388524 352161916 383745159 798964644 322751183 927780375 619018761 43642841 900354850 830007422 364878661 796317694 601688712 204900860 35370992 133787378 296692472 890588271 973019551 632207199 686679121 …
Output: 7733014306

Example 2:

Input: 3256 990345801 705653210 846348773 537809506 61514484 88581159 87680169 598110175 646270339 440347816 565175052 611866866 854917165 933823280 942922671 60326819 881985096 345587700 148296095 265176806 560621942 5828188 114916747 964434992 264756251 703370132 477041757 128131357 128016602 801522472 501195989 59304461 773057449 33092974 645071977 349706168 433639747 318344013 132065196 66852640 137875317 193300980 22085631 125821327 561319413 84431634 342865374 176869835 113987502 343509817 385532738 423552222 912473177 346742957 62440877 439392061 823678586 824194940 187725589 319902612 791953105 771338443 320311141 580373009 36256628 8106993 532777136 238439835 540349630 359327965 638379589 535346448 858815391 667501097 388162888 562824095 482174425 828493229 457283519 797913064 76847133 2…
Output: 7797661794

Example 3:

Input: 1835 643679306 610587399 289511259 443466358 692121664 373155279 42498420 492607949 720873593 796345515 161837719 112122540 669333209 324201505 198477428 844938114 969346915 255958687 440119238 761753549 424593091 277010171 264628432 553000653 137373037 829362877 417240145 624101177 528435499 268201887 181506799 809306997 914670638 613903631 102025953 565977129 240475554 695205539 461929100 253200923 622753270 33111625 620134514 622149201 256594890 305049439 448242443 67375070 889705772 317873060 192298176 844650817 64248720 341503400 69726444 270759469 591789358 250966572 774948677 721183840 68895678 985120191 623448150 497221186 789153908 475370911 640227178 211118222 879741460 6490461 988262163 729940238 863855674 20963265 624946357 828586549 915765634 249785545 462106235 834885015 2811…
Output: 7194983376

Constraints:

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

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