CT61755

The Tempest signals of Devi

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Devi inherited the apothecary at the lily shoals of Padmore along with its curious bookkeeping system for signals. 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: 3395 362320167 812068058 650331742 698382862 593467840 653549200 713323213 312659941 997384999 906931392 913527102 315210002 849723070 472375550 719601252 329213066 540903889 400531794 461315861 609457841 580609421 535877198 143448303 171337777 689059384 518912041 740960947 335026107 816613199 794107827 54578240 449714736 513906015 268514304 207724427 101072324 957410103 122419699 225513188 120243897 492837050 434786981 967592058 256956564 201383424 744764771 129334646 986957208 466836164 707566802 696590074 690580007 517865329 615572204 133131861 162252694 857635027 257942673 779559842 124105823 691871539 296283655 387090200 905803004 819101407 304077939 330492562 136289304 293873644 315012793 396072921 486534872 832544910 655824734 947812880 90395196 253736375 683933377 763761276 9264649…
Output: 8542235870

Example 2:

Input: 2260 72911954 138069446 853121504 945425026 544640162 274244686 551114318 198094013 611362383 389976114 48872807 453442204 635014602 78260977 843063749 415298451 126450965 215501097 949374370 272691949 760722648 63911765 538749053 57331572 556163159 278417954 945253830 809582444 427101799 943914092 853437391 683613010 903761841 269564174 792413847 357667981 361076240 468704927 509645227 577351617 767256405 878424637 806668569 34172328 743563657 852803790 248558874 402614832 846669723 361338660 271771011 671577368 891530260 155176364 24739443 3173117 430298078 426988971 250032250 892195057 446513409 623851304 632330064 943676931 259873640 57349153 670768758 382181620 535101096 173655817 365752212 963055586 75582318 672079286 597565206 527813128 199033897 663700892 292140236 12302333 7979221…
Output: 8538659552

Example 3:

Input: 1169 626548558 347706565 554728611 419879948 88466564 71944000 78828622 967561830 60685454 797996413 823457441 569690398 17171798 638918395 623016204 947347648 642170060 820254940 684640960 986965698 207620923 280067574 207033566 593469425 44075639 412000489 995557204 976638577 469298044 258309026 576430494 147429678 68147116 481104257 355439988 600628083 173699888 831274403 684357284 626027958 6552828 246892444 695330748 91809244 219860681 652460484 659862019 993443613 880329270 905418933 441368029 336458064 768724489 77239517 117903391 394042065 370988283 399308752 971604070 772946208 90894423 396711299 52673392 752103178 931355756 49067376 354271584 220647978 707039709 833010240 622198324 818031357 724642009 611262069 228801326 903737270 399414096 230830602 405341425 804349721 777932607…
Output: 7907577748

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Tempest signals of Devi - MEDIUM Coding Problem | CodeTikki