CT57441

The registers at Beeswick

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the honeycomb cliffs of Beeswick; Dev weighs the day's registers manifests and starts the calculations. 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: 3520 462304165 872116180 891013519 972681934 760730940 45615241 771585685 217278469 510254909 779977934 695641396 423610549 893320644 243284422 923300753 643325123 885209863 979008672 773251407 270158934 585556161 409932970 864767132 192551906 944073254 315008882 265898248 693345472 819592397 560384594 571688245 114934887 111315016 529225621 812877457 420767318 986448397 329634578 906727387 753100500 867335424 378983610 733116318 369402681 478756288 253424380 916402483 188356623 446292494 314970369 251529472 785812884 674133803 854484102 36717015 532923379 821465706 371706006 895101738 543616536 470464960 6658509 257309419 300921867 389212394 998229533 775528098 450452892 148577620 693040968 217820041 739290149 157996828 434781394 745428084 755882404 325784328 206503906 778711447 573300092…
Output: 8227870728

Example 2:

Input: 3534 899073120 829495050 475326146 599541673 630295499 284383316 180222879 140711694 997504349 238195898 279216471 33071739 671009029 121082841 592827823 301046777 279768227 17339195 776428866 94726562 922530311 801881111 343961321 531334745 645499003 66681171 742964098 477156557 382875594 220358061 703618009 323577956 771490498 708979281 424755035 99431379 630814192 795768092 381989681 350489098 504920460 43956709 740836221 969343500 854336074 16756436 564856833 393908853 870872228 252321181 466010855 448582965 66112371 863108758 633102329 967391470 88838973 737441133 910915056 864325018 150820050 516660931 824346134 237821579 660505269 906976502 325550166 940171241 415608370 780969702 902755501 139248927 355279802 549367279 860968176 217728317 309633049 581242314 510877160 937404909 2761…
Output: 7192985184

Example 3:

Input: 317 907117905 112905118 459417303 152833144 130916947 504053679 253675711 100642590 359240952 964566899 547065000 919465462 357851398 373683651 515321014 284830779 211755867 17549179 255898325 765206276 894289646 142361421 621612137 649705337 841439930 690970338 66449921 578898602 201120068 179961781 897391449 625087624 523945762 397501664 5732658 216064423 102825460 34896027 943335843 209035995 67202177 707757216 204994776 292349165 353405742 61439910 319142177 135151071 149410674 53823439 339078550 574767624 554386068 282505123 576940423 984283707 397964564 68349599 96882296 617866652 106060563 238782817 768005207 851603413 31756528 185303905 992339195 327117092 618163718 772560936 644475279 173835982 493941720 663781746 174479155 302647068 283158346 819391640 222925552 960618606 9866152…
Output: 4457391336

Constraints:

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

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