CT59509

The Grand Facade of the Obsidian marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petra inherited the stall at the ivory gates of Alabast along with its curious bookkeeping system for marks. Time to make sense of it. 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: 1548 959503441 412579158 384196430 8259309 34056077 906936086 676075916 585489321 698539225 530465021 142988398 103198183 669423312 315606200 334046247 30364080 954179830 546087444 154326339 630914059 742003076 21570229 730992135 341343427 239204182 473002643 154613983 104379741 968606912 621170463 206941860 162677994 624274607 309216722 575561435 92943858 965035833 52277319 879388543 418088466 203502144 829879751 319576947 575487980 427233935 792355097 470956309 761648011 396894649 277983513 874171866 16448339 318052104 476899791 148402661 173179276 289371556 430845084 12287177 813244436 798242949 605142558 405522827 493141876 89789079 65568354 288888614 473125572 304127985 941111047 803145227 114271810 982111699 431909503 935518190 316276910 47798799 691465040 181022591 810725754 1303233…
Output: 10158749370

Example 2:

Input: 273 778447234 185257210 82672975 488035219 838141342 178302087 281017529 438593163 99443613 432791360 551943069 435336392 422443021 768738751 800928992 983272058 578398031 780719653 856348572 643778832 499474108 236001185 944416639 817353526 157157518 181366603 951804807 308243491 268232099 551027218 656690508 678975664 959066150 425307444 106678527 191389290 105506650 267990462 781550645 41969022 181037029 289722178 701927378 166005231 735628227 586407068 487774133 652616187 267559656 986270250 262848928 595429726 595740060 825713953 437031241 150084559 875568938 643473352 24577263 552855394 982218772 104211194 220277921 359750823 805680109 974058469 304550805 769965555 139068518 955457821 616430443 689398106 146464420 681923351 682376939 991188009 435208806 500963555 467707911 437484604 …
Output: 5069316252

Example 3:

Input: 105 793652989 353262135 919405668 163727019 890939794 583568695 923436511 177857732 885529848 84173764 785735071 300427283 925662396 500121108 61169933 816559125 872701082 924416304 879610539 272499969 631348107 859438732 694584590 905924967 697867486 903860724 419779865 617216417 240650190 320617576 56005313 849210467 421930196 611555930 396704187 129286247 415576253 962199623 120283978 187187570 659675090 570519300 330675704 427007014 766438180 262268624 825778608 799231865 997897268 285218058 175192105 471138864 13164799 750979501 741731421 484264775 8313064 28772278 269834454 845775445 846241232 744278311 177316900 466368789 462503163 626832562 845758657 145207604 935986187 523763952 456750795 280851544 303468895 576116797 51271484 400846221 756162104 894189718 352387412 471210948 6873…
Output: 3788088642

Constraints:

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

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