CT61205

Yusuf's Hidden ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Yusuf found an old ledger of ledgers in the stall attic at the jade shrine of Serpentis. The margin notes pose a precise question. 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: 3782 95158896 127682047 194289268 820200186 883229239 770197736 665727374 308850189 137782745 796629160 664753391 516574364 525515390 754991021 275116504 463973897 604522400 518055931 821396081 327412015 837437682 580527013 206880433 867809243 623007875 347877183 106038845 369564254 762079238 154472725 262753786 498552171 232146782 450164459 51592838 971296590 879759658 935890094 408783224 522905604 706475378 281928469 172910168 427896816 951427749 134245019 982901719 264625839 744094809 162437979 177561037 682177711 262314373 446315445 374213226 376993412 715750815 347527119 228662494 937692414 886796629 170717963 273666161 673968184 755766326 546475868 741915909 199498767 53395332 3691455 470993703 339224693 962104487 530714720 60284327 141494354 521196088 360146030 430911217 600825349 2…
Output: 7487366726

Example 2:

Input: 212 373282299 318431565 767502645 504240210 315178074 441007077 546870215 689721622 464093387 206840020 241656702 426723399 544081550 324696198 778311872 674433119 227051967 17270093 535237585 530238590 437915433 788891482 701219260 753188210 724199750 442635355 619538468 900464431 692120165 897194482 740875427 35906739 93397292 272827334 67841780 502911050 107116843 840446529 7874820 760479901 17629323 86575026 339054140 525657306 251193308 835097763 416086803 385869921 150620649 826412740 859650865 353649417 656411722 26430059 96994446 103799919 466097741 890796085 414101457 49177332 78808675 125696087 507775381 336341453 18509437 748877840 41100834 975430439 694617331 93828268 633341730 438937514 316547045 772155524 509674563 911737094 588617933 367828523 456692165 404156182 815167404 2…
Output: 6790380176

Example 3:

Input: 2500 660933061 713812125 900145495 124319361 96642211 174214946 982670878 587448468 872409556 835669645 858481228 44854179 261213238 875269448 133453604 77884163 171943784 685738356 920864250 713368518 492235390 271833580 753187347 955079254 604864579 496648258 124726043 909627792 176981173 619931306 843607979 630762202 443499929 598984174 912599254 867693673 808580552 421301709 289505392 489007961 213639368 796603793 389052821 620476264 366300108 394769104 482651359 981547353 650812780 130112645 123919687 974493451 966492806 170576519 435301099 959516355 32969333 375046044 413855755 993443738 33372281 626707028 272750073 529853985 357070980 669370369 572449242 565700517 636329229 713154834 196895889 137628366 853638800 758200229 134169299 353755540 400882962 232668852 83498395 968551952 7…
Output: 9195191830

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Yusuf's Hidden ledgers - MEDIUM Coding Problem | CodeTikki