CT60460

Ravi's Ledger of marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ravi runs the exchange at the cliffside roost of Stormrest. Today the books show a list of marks, 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: 724 5799738 570118381 292659667 369120664 170739136 445383618 132506039 418098614 452545439 730377382 532224513 642699292 916103904 231404111 614936557 496798005 56798085 217263819 546137040 838576073 319710040 201612491 887530837 555902385 382727285 986666810 538967429 821129204 73425516 986354930 47023090 127332571 152424770 46222437 84257708 332717558 996268821 233594611 901588622 824494295 64447332 508654659 249231892 543664727 611472753 959227820 201848132 20420941 432593464 260645835 879465433 976853390 369613690 68132194 38178378 498361857 675344533 442921191 860360484 84756438 856013708 823488748 250245581 651498541 2364016 759230394 347990292 506278955 663347619 201107436 916477242 796959716 582293443 699943347 636883960 490203868 310971882 141424730 478288119 518269411 62462984 2…
Output: 5699955454

Example 2:

Input: 416 665858503 952309994 411626525 106416062 415771263 334059820 822950383 737466557 447755214 262242970 752524385 357677587 46829407 339325188 347616329 380276875 143530479 904381272 580118536 573460237 533591566 414499004 945845771 61001650 254264465 67735303 117413513 769358928 18239782 806421581 944592999 60496157 81215534 863796132 178380886 19054621 558470771 781704127 251021207 252916886 757906341 830794416 838767279 126053889 960224270 108527136 272746179 561316820 778014617 952908063 105457637 122512008 133893242 861291668 590986285 518508242 842521776 682058464 979953630 151795839 254023231 187555040 392185821 542098345 89569762 643577915 893499778 183910162 234444577 168240518 138969174 79368518 731322210 4707199 141347971 614164594 578056596 60923591 954080088 313309639 11283739…
Output: 6934672329

Example 3:

Input: 2418 338910030 490069798 625667466 46147598 511936995 586958727 746735642 748176689 384583018 862321683 103748959 628091293 532300728 941572758 51276128 862194589 695407804 455710247 255524421 244257553 772813800 36630194 28314072 566241082 485551195 335626775 976058655 940594408 36618127 360834122 443510956 425629577 507291271 392374960 546510429 353246725 263627241 304543424 446688692 642450603 176569342 261761816 47752321 700913504 260836227 214683626 191705121 997418607 633168342 870349095 122160240 224935648 569726495 834952588 776396142 19108119 418141674 264786231 348698952 453257201 903548802 651999276 145385079 919654848 331052457 276682596 620165522 739393773 579435070 30710382 930586163 274538851 178358494 839110761 334829188 176543414 535257492 255900791 194248290 186875279 147…
Output: 9042020280

Constraints:

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

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