CT63781

Tracker's Amber beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the salt flats of Palemere, someone must schedule the next expedition. This year the task falls to Tracker, armed only with the beacons register. 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: 379 751851672 368453206 266523982 184349294 951258247 698311020 77451173 178621965 431243080 258894601 281532421 705748937 726169339 932051308 884667990 898284406 18331707 461453424 746156119 556684649 61041367 743831476 807898608 280085377 482996996 779538579 53211330 660606710 726950521 865082892 147317103 360796982 746968023 350867060 565582209 382525837 343806008 583126454 254110197 430272593 543344916 907775007 550247384 207877679 610603320 918474930 789004379 531942369 976269453 578408708 174395698 738218749 131330139 609215388 786030168 646027195 98206025 563917248 896162794 139635259 562092256 145614441 288729663 240859967 432565394 549861409 30839455 934842846 449486170 711559261 5441734 575466281 780102322 962473046 459940333 331904750 686138977 859459702 339091580 309157413 3019…
Output: 6691641348

Example 2:

Input: 611 303402269 443513512 10347533 595844943 210329181 670639690 80909523 783373927 346441260 485309783 369783666 414485346 504770680 11736332 708764097 413953490 964696849 406908068 293465989 763397776 32770349 356848613 660952785 964671044 174960541 329454460 136058266 988511909 341755757 720005699 968389372 161832528 245654448 485462791 874013304 945458390 244890187 235744404 989742107 604497054 117652027 909636990 495354519 946064430 426335648 129186251 644646936 878604347 641467581 252195533 325363497 747358088 511115895 155817288 468389900 982651531 899406795 586733190 861733314 419206185 762086435 198406037 722239308 752481007 843608455 936116384 474507617 15378295 662096191 452249159 198756935 192131001 879764146 184624059 795016009 187016955 806052155 682227795 797850102 462904074 4…
Output: 6986984088

Example 3:

Input: 2012 11707171 137702670 610324757 548932316 518841397 962527372 510414506 938711209 348364822 260927160 943370968 969099759 343004678 754157126 348209267 760872308 272650061 870288056 45918262 845408420 121947599 633200493 31097788 563941054 777731180 124930923 392557068 514903489 676236238 957518987 130124578 589874412 877742961 677661972 479003069 865311600 369822240 179059515 36124515 688848672 474463657 974504561 434327122 590535592 608820222 382495295 576184562 726087999 921912895 325397731 236182879 960052013 528674523 684726406 785786456 521985150 16147615 478475982 633237260 829504849 962758278 300404799 681017448 67908065 672837124 612516856 559854965 114330190 604177501 206751117 860756607 643604559 646649682 540089869 10197085 702331703 356498416 291777115 405342022 284626698 91…
Output: 8012710629

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Tracker's Amber beacons - MEDIUM Coding Problem | CodeTikki