CT61780

Vigo and the Ashen registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the salt flats of Palemere, Vigo the scribe keeps careful count of the registers. Document the rare sighting, every figure matters. 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: 2289 675368412 891987408 795272251 669012494 424443235 465230538 481204390 254030330 575222664 723653020 758702066 932344986 62542625 919763076 628361689 662392064 356340123 184466015 968602427 397059533 99332254 785696493 421806998 887155693 490395787 12312572 192852281 685872150 304871240 94539091 118589497 73191146 887877144 125242006 204374868 814727845 910249396 630922139 436674134 599437615 438497198 129870311 478637099 497757859 246163123 232018066 59879568 251738322 272818897 9315777 815623060 715679483 439388935 873888845 344349328 97695337 302431240 405942224 789533072 295782630 823856015 272633204 671431056 735351018 388820790 384013259 361122698 680438655 215934629 888226780 37601197 747068619 234005956 820522652 503776263 517294518 668437973 490164841 452229843 51550561 701922…
Output: 6448957691

Example 2:

Input: 170 680011360 78745066 100059234 413156490 244729107 55939608 140978533 423587541 603546116 269623978 89175817 469027783 486770970 983937866 182230454 769031715 269425761 446650374 500130066 800033140 367494320 718462733 865600983 91660011 548325221 335335008 426298784 679182476 263621579 66712553 594766179 981311631 924620332 434640944 693800110 802317024 656918155 322987262 117015994 813369919 210889255 247348343 349151541 335110834 811758230 784527617 852394552 913842677 128920998 447744546 304542791 484338897 63894681 80495860 955902792 862929557 618108330 249852114 581577812 760784286 165443755 47538523 956557212 250724594 78742051 505483416 449010642 427092519 302132431 607410109 953962115 212878337 863695925 434084779 771648234 80596804 504808097 459368186 451876874 208912394 411725…
Output: 4582365300

Example 3:

Input: 1578 336910578 35809520 576415380 278190561 701796980 428853085 621383994 826547115 523079504 743308827 367975961 158980881 842878601 927279787 341456325 113781500 714333469 868369391 661257896 850884801 512170034 599404682 129620941 476997981 359110936 923476123 596906379 867051563 998361037 113491253 637488743 428899283 416514807 983762743 393571317 121828967 597516100 421350733 491428073 223637522 860447463 603206285 137870260 719048921 948576054 415544405 675422385 806198132 769472141 504328652 184019402 275827437 483934838 6776670 20247086 643837728 328983906 353720235 678078141 662387419 832471629 7630732 321696602 46911297 424958582 257157939 913482712 53984054 576862931 221291973 838515828 943547564 654213066 765263669 542643718 188638283 785820956 622112431 119223285 702514764 752…
Output: 7203810390

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Vigo and the Ashen registers - MEDIUM Coding Problem | CodeTikki