CT57345

The Dusky marks of Scribe

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Scribe inherited the kitchen at the honey farms of Buzzwell 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: 3937 718469033 940376275 352566585 800346859 384869963 379324807 145243039 788267977 952294055 696899593 89169150 522691387 787655007 531908621 838983802 743438496 379404975 886337571 4999473 70503615 19314680 509121030 157973028 71629250 410532328 546788862 792065046 781822238 720799909 577903398 808460011 555558636 296731096 387641599 674013330 698286156 704421169 934862956 302054475 225352639 628184538 218876083 992337065 855746650 75167745 102868448 778450676 328261651 169174740 658300281 23212143 470428731 201434565 336091641 948735105 342944297 773154575 647985215 400763652 575311486 364481714 414846137 784191005 200349296 44876394 242828500 248318145 930158732 366164794 942901284 655128328 703737837 570107093 618459135 776152020 426577623 671347632 450038123 598554511 147490695 5705…
Output: 9384332540

Example 2:

Input: 3926 782092681 152864372 357474914 161655179 845296337 182287959 919931683 718147330 527256791 496777098 249982104 425920325 256443895 993119997 974846235 27423742 309354701 274418067 617746746 709627539 894053775 112652872 321147085 369675881 718197948 902204679 559003483 618463649 767565630 761727487 975162740 938366409 841901772 661785151 550774600 330860756 613312158 29137762 183269763 626355424 723257765 834589288 488544636 780839651 392079792 781391022 637890394 486513142 264986903 488611557 944544678 566358769 561346679 999441798 46586242 824574862 468910109 642715837 35786096 579467062 492467069 610550282 956356032 247706678 235220000 177067029 738827020 321670167 566475366 12793589 816285426 157251649 850446874 656367837 792798447 644434042 231575562 288967539 651650818 567074680 …
Output: 7588982609

Example 3:

Input: 3179 718128263 416254775 973562975 170733543 573829177 770260175 571620309 698872167 70896929 306384294 427400648 55621589 294247009 954289068 603661437 956234231 401571771 972398753 359190784 366090591 543558000 242224633 577707302 689339897 952428053 664547471 666310821 939199235 210952937 185920070 743926450 109243456 545683906 444303175 44392637 582597421 524203656 860396221 669547477 825805298 520577441 980929187 443564701 308979505 594217605 613218454 944098891 498987297 11856395 747675257 96381671 159980015 762457519 367970808 142919586 6618174 518487507 910136631 661075527 357582723 77953133 61049916 926080806 270581692 222752104 325504855 738302787 289931614 72194689 552898984 886342872 873054691 992472927 61112144 70806250 488744605 598990642 161397357 116573778 632144202 3354126…
Output: 7667610244

Constraints:

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

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