CT63238

The Grand Facade at Cascade Vale

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Emir runs the mint at the ribbon falls of Cascade Vale. Today the books show a list of beacons, 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: 3008 372302951 644071316 199909707 170365862 972374564 302324253 83050812 59620338 594099107 315758247 95907396 988051199 87447379 93985441 579174177 846011148 199801615 162380524 743574764 203772047 251000682 513032098 33365911 543756162 6192089 959603818 50824509 297018767 245957032 489874833 766994658 97942746 996614591 955540578 401627050 376992886 283645674 70395384 96152422 387092352 104776183 913103875 324672226 799719658 220735916 529932590 673207110 210125928 119057112 305579307 282732101 6736367 23480957 948542606 625700768 377488943 438500992 830721091 528348501 486195237 757887925 8574638 591841919 193795487 822427596 685801869 337008341 457871687 265874131 550614334 56835696 796987321 684628529 658803428 356855787 669859471 24464695 687353846 751989283 560746233 799988316 5289…
Output: 7572277130

Example 2:

Input: 1926 559264056 138832275 350953101 626368471 680224708 81954066 391848163 53182086 914693085 667468301 888083992 917694328 845524821 156135380 105128711 413137901 673744235 349885750 562588839 6521838 695380243 762399406 233874719 195759780 269781142 851752405 638775803 366086768 228457944 387932229 726829451 269366540 288604839 985194851 931268292 589125074 12269631 92273912 523507474 960732163 829425005 414712495 180826477 491701879 863914142 435603013 499808776 272090216 847841796 865456493 767155375 153296270 515733897 861828126 587506487 604659834 655552313 604954022 618122449 774613633 328577519 277563779 681191576 99073879 148678104 232601800 258224456 306694059 852901828 32450294 598694703 629307001 202052693 709564774 286143623 475874335 167263564 602324219 175958662 788206943 645…
Output: 7970562808

Example 3:

Input: 1951 198270264 178222909 864009623 151343970 532771674 448235232 527581077 333036222 491011510 224365180 246692409 679280807 955015814 562664025 179035805 430076784 806112561 177346081 344258956 341836563 123492095 251407015 835564400 442180791 824552221 473969687 537433663 194486709 989208286 242017449 133807818 634792368 337462239 738388142 68429086 807635669 532299645 943597032 164575667 700747502 330943538 638643215 183707182 259095789 623993741 828146360 695522579 844316606 734386675 423214046 13118952 652730252 411411430 150253632 395540914 909394359 246372921 735808747 845917021 839612448 39177266 472711175 858593182 11532604 852256997 741538125 890905816 883289830 676247504 333894329 77766424 298893387 647200082 664135387 888115261 231411494 478852406 246143684 80427373 684417664 9…
Output: 7841094900

Constraints:

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

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