CT61302

Pavel's Wistful signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Pavel found an old ledger of signals in the archive attic at the obsidian flows of Blackglass. 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: 70 300414813 965819652 946345217 654032459 946630870 212523773 972874845 114400145 287602472 986212234 213282455 109449228 327241951 652086431 901180818 132959258 147413087 533322448 421384639 228636863 508332039 507570466 293850208 597535491 918875141 716494358 433539989 829094528 766415431 512058355 434588960 108231762 412738094 696793560 15376132 76554595 715448675 653932060 226467824 83607505 26452087 262205359 5238227 286338208 971426408 828758271 535356294 638288093 621049072 45610081 901036030 209287082 81751216 269139091 273635303 270064465 920846186 433034496 243003963 619728200 230509506 826468100 25851130 880081233 492899662 476384056 461970684 337835686 777712518 152002096
Output: 3679879908

Example 2:

Input: 2874 876230831 602147920 462991156 974219312 882427310 276662352 206417765 300133336 193368586 736860095 750798191 190263085 473049420 122866084 309656239 435923040 72960946 723258381 523041593 268511129 509817622 920091264 81847101 489105508 349614492 8955000 512360623 374162702 971122707 50024890 897416161 644141039 317177130 2449013 68939775 181940563 11247143 687371374 296908315 63486840 741431824 33256739 743725126 878044154 129259462 704173370 361225945 402040135 719391990 127541785 287565306 156635150 426575307 116780066 560641275 365714560 702672817 266488339 700181808 10329654 856761164 834791027 390483619 466566291 130790603 345134316 409085993 2770514 212264910 228591831 663132763 293364153 683780800 665839970 761185385 251853864 848203859 975935696 866949708 707364833 334828377…
Output: 9543174868

Example 3:

Input: 456 63583704 20903470 727076800 786977952 442308727 767483385 466742635 746483670 109786928 565974695 885944661 564409764 624886507 411502966 350292106 780711460 461125426 91370720 441610793 393162061 654581690 416459263 765280611 85133235 232240426 573633675 387680277 811355111 115520437 156113394 909010618 933016420 426565876 744181835 906762911 276553946 502579427 174063867 405637261 573662619 151776842 966295160 921164828 105550591 984043403 916975331 862455262 198914176 607212654 727808310 470696457 495627657 220159210 896696649 933215826 960337900 46559124 324209126 82299043 889654842 46293130 578674392 443127784 157549371 73762258 454052426 583759488 470218683 213892313 960876643 261295577 951785589 700624449 246680183 116336607 985568863 75245516 265720960 182239029 389752377 60268…
Output: 8521265160

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Pavel's Wistful signals - MEDIUM Coding Problem | CodeTikki