CT64769

The signals at Echo Dunes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Lamplighter the measurer watches over the singing sands of Echo Dunes's stores of signals. A careful computation stands between order and chaos. 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: 3684 582589029 721124606 800113876 167119685 233618395 623738397 235293379 225891397 851505324 317053586 215031322 23008367 251283249 822269565 654853243 274500616 101174150 948897801 993099121 202411674 282040621 528237376 907179621 346063750 501289978 248572276 433907938 739467990 250003119 988104361 448695408 563707077 600369049 237722772 2284334 776935211 792691490 37942978 989857632 447266981 685766468 740602900 266405177 795940546 790531815 405533784 754253327 17896835 222690283 1839861 589355384 455219811 207739092 586610575 465475904 928066891 235077775 254982955 884350509 445246508 801825952 491268236 625959697 470077957 688871925 531347330 494070602 748077909 905734244 310779308 626162235 348301782 774526671 321205694 219940967 226120619 470918971 145692924 270095520 931825247 69…
Output: 7543777285

Example 2:

Input: 1539 811084434 903026914 416134106 635400807 675243391 113993685 243719736 380414831 39656688 140098517 939726492 159069252 358899684 58594606 462832854 112247238 340516975 325077193 99386518 539760436 898547982 225572589 244604284 79287978 12767905 943538977 370468340 6433794 557604716 653013421 408295090 520552369 900048858 986763415 575565413 339022352 907347604 166204014 99164684 68022968 220720457 78967502 792815701 630538881 827958449 856012534 13122873 231222800 356190990 951443309 114285453 81277939 617506524 321776381 572663754 837159379 118317718 545674301 880767009 659543622 803812570 83487001 345881653 710761961 91299182 954469777 619033137 727228129 259623747 142290909 9771419 307987267 54648805 943309273 834530549 967988572 761234292 58914266 599488471 623258581 732834716 694…
Output: 7618012503

Example 3:

Input: 3116 765170391 971145718 685017183 132953748 942445630 582537452 437821759 485541262 185339831 845505110 531417514 108132157 700477647 630220914 785346770 546787374 262118719 205459752 515378004 613099799 583982436 722883476 142895430 651091339 83521337 423149603 795247615 418887525 518093880 271621815 70417603 494856062 373296442 238412520 649584923 267162561 641868337 451579666 82427095 104159603 409368354 843620408 696697319 610532387 501388614 470214130 209325353 382060161 476366279 825815917 11615749 487248400 201501980 226233749 944427069 792896281 294148211 598935473 357794743 446844967 830527311 151509712 679698169 184652507 169175378 311888255 233627377 711408867 623045947 776894034 597735227 748268655 954783010 434711321 755055024 319245028 997371294 595694947 291131626 95337846 …
Output: 8264774468

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The signals at Echo Dunes - MEDIUM Coding Problem | CodeTikki