CT57520

Lamplighter Counts the beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Lamplighter the dispatch writer watches over the cedar groves of Balmcrest's stores of beacons. 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: 3851 897765462 763083445 976258249 935735322 422449046 994990227 454711886 392962237 757328594 906535169 199320691 610573728 558484488 785612621 241463644 701645205 342992061 189364108 197419833 637404683 603132853 936223153 572174702 303407993 998491290 650008152 989196729 637767944 273330521 349259391 394925459 651346786 888052308 809722777 881881516 787361028 433588007 835281155 27199207 210018813 818741533 279424309 253704000 912295232 734273051 341239433 725909716 992950508 442592254 665846191 892592955 445296264 212158589 512575194 616127952 281538237 102904022 944260357 615716719 160425374 666277457 376877315 301783934 605335829 224517498 436757202 627312230 837796566 877023115 437955512 887301611 209822425 311441445 184694234 409035754 748091576 135296436 260227452 93513344 7429416…
Output: 8761094940

Example 2:

Input: 1444 354090236 278084927 436998766 30152498 769467917 990192205 880105284 616393050 346505820 48515661 490433117 68588438 259146404 255786634 189919032 899320711 382837848 583533566 941522770 566997376 308006804 353550098 147739409 213177796 239308876 566724347 697502422 866682988 271507021 533158373 760839254 193206798 437806847 102993256 390818188 882910393 215486230 648318865 533464723 209269109 648448697 993889490 909772431 346323037 493598376 851506015 271024649 524121770 500200791 447712508 238782825 261945167 371628033 378290774 92666781 232215202 273558795 841653370 499848662 83666851 296818876 171205021 660975976 831792748 526773302 90506491 362268640 272014870 788447113 279764209 244461047 263810003 364352876 826897515 762880743 659229535 874326868 270436724 770142023 391540358 8…
Output: 7781017143

Example 3:

Input: 3775 904525246 586973602 828965428 43133569 733980942 62364173 522519564 394348241 479590019 959728073 803462680 352086699 310098205 427154910 617814888 212308478 897052877 40529218 212932314 333828527 243595687 641134601 857798175 33796083 136581800 719050711 418741703 648666935 289172874 1423450 646622514 293613654 299801460 285343400 64818485 688522747 706872945 107847841 808034467 791999162 352990619 326787452 953979023 623478839 91380882 759260918 679136139 791834485 971960571 527043383 396076056 266629116 607986632 224749706 362463228 655099075 363799791 653899594 687672002 591002205 93963687 179213363 343941123 256589373 486508359 472961958 244531476 340061385 921825869 408052586 596694634 234742160 855074084 102412073 747426554 527386880 152975717 205231064 527970555 442405787 9759…
Output: 7679286783

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lamplighter Counts the beacons - MEDIUM Coding Problem | CodeTikki