CT61406

The Grand Facade of Hammerfall

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the anvil district of Hammerfall, Dora records each registers in a worn leather ledger. The guild wants answers, not guesses. 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: 548 690404638 387085768 599949923 8033683 482092404 844632451 274213305 821043795 76373131 23572996 830802653 947575078 831565063 774600810 234840803 668206885 740673000 471081210 752506896 105887471 788704403 337893009 840855025 777868241 988317584 935186821 869447341 924757489 419428713 750435827 510209938 78351154 896746143 441197954 464148499 305627969 982203755 805112365 861211726 726395666 946641663 356011288 485967923 404743513 239520861 704436540 37554059 764796027 557503999 10090111 195022054 951918223 306938487 962275703 298214057 193031516 546684258 566095343 864647140 35452300 375142184 28032095 476559098 121907143 179239726 493454436 661758997 984412033 263036376 619472205 440456917 861492830 903456417 569174418 603388917 88562936 380183846 562385155 646076536 350744581 423999…
Output: 5943077478

Example 2:

Input: 3804 370956241 751422934 269086196 336350850 136464409 821003692 323386968 835184489 737781447 990298014 143655146 621295943 101825109 991598733 476421991 294254433 931665867 784097947 919633240 699633756 728034617 210231226 806919807 432216672 174174184 635115798 402660140 628181515 100533193 722006428 593840847 166920957 350385090 883410439 81388829 520066288 599274241 546921962 210977968 673033532 61194156 526615732 11814658 345385437 202255504 335086505 824699242 863910699 413308300 587008442 900295980 970745918 754168398 732334911 138486649 951004387 6992072 687684001 679938395 569952930 253112459 767595285 923412547 136246428 999072905 33324917 795625848 562900665 660956714 434840172 333993075 567405207 458622531 124819187 763566998 708731734 871813118 305524459 763490030 539438112 1…
Output: 8868384256

Example 3:

Input: 1727 211968734 808584839 337278933 254421111 657725671 756298552 339895208 620480949 88208274 647574320 863643517 467102879 709643214 371666300 269311634 81199427 5671776 921510174 669424239 326466503 813249664 482838984 593218183 580681980 100933205 710376282 507338324 306040739 72993945 514405616 44859981 940969858 342028969 194633521 41697865 586697476 45285078 912721375 676855463 13194185 339818061 89398961 256295374 125553507 986375089 520136082 103198185 975208357 136169300 889543371 911893919 954471014 509063609 877625435 190975550 872153802 266045668 463733981 804904445 827671802 721371849 612555759 441619286 692962467 789112268 434132929 846417256 849281322 39698133 46047582 296596150 882651097 893064231 873210693 541812887 306501005 92395381 355705365 312037627 910941497 30793706…
Output: 8075962256

Constraints:

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

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