CT61387

The Zigzag ledgers of Envoy

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the honey farms of Buzzwell, Envoy records each ledgers 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: 3290 44086461 933650350 844336660 915746412 900214843 927808244 208529671 509170202 211531908 472002627 981176154 723437535 201306591 934855821 620150780 167215372 690014726 478050543 848168268 445505891 862946271 515982741 916151264 612940112 880954978 536856470 744186846 63305630 761336611 400028398 534117965 21379191 403956717 55887198 381906735 388618866 655554392 972680883 61396673 733406446 484408656 249258144 320113570 564687320 138256412 265005363 641659469 178992042 981569400 973716494 248443590 603353909 476386550 493317413 43810198 477331072 186435230 935905143 236447677 104258709 876787797 963941553 505469714 547098857 391998787 676828501 300473047 340647500 933624181 219169211 507519842 425515737 438818010 556172192 53903901 12552262 722590856 311031335 290416834 601855049 714…
Output: 10148526990

Example 2:

Input: 3998 748221039 78972542 247680194 740389094 543184097 412894260 149105159 953367440 848111797 494118984 150109980 796704323 157308385 782818455 140967102 351277155 180618273 226371452 108569875 637507064 730338376 873870012 750902448 54495849 395064207 354586609 718409153 290669994 656398768 587046334 144023830 443255947 192056703 647212946 951628173 497633576 501931319 115304208 118711695 544791390 921819863 130821230 811431173 61148683 506889233 985344137 511610384 856017038 237773213 187313158 174396255 654557940 555327255 259597186 331138552 830929614 366024685 632997806 657214437 274293576 742869394 713024877 161739060 545310222 698097438 985105167 381338824 337666744 538693254 340208347 862775343 316651318 761096649 57680580 391359126 492942349 58575574 729598716 783712024 979214617 …
Output: 7453622613

Example 3:

Input: 2491 56194327 691516952 81267862 862657968 131050511 225057532 121867704 204443780 175519999 471594553 728353653 5429815 905990356 636290073 370247144 594462088 16779461 189045458 984127313 953030101 807273170 710806079 267748848 428758505 852592916 971242963 633173563 497660454 460679292 334004137 717316332 22651932 909511958 99560778 597688059 293428108 534613195 343229857 539989618 392582643 236761122 136140043 130210839 564877895 752926714 41791380 559364444 559211502 112317907 901770448 621535979 573751090 635198455 242671324 933405633 540057762 946384488 997505029 732959614 824222933 889786495 898151087 577137068 348903068 961030646 515789045 964912402 541768666 352562354 296567872 780890599 548953262 448609022 575365731 138102081 28836376 497345944 385955387 546520255 83546633 34255…
Output: 7758419757

Constraints:

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

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