CT64477

Jaya's Ledger of beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jaya found an old ledger of beacons in the timber yard attic at the desert outpost of Sandspire. 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: 2033 746554057 763997101 358868121 435734197 546238386 319556075 745147191 787261267 873136654 330107856 217915432 28513936 681392045 150769983 695030626 893826127 782730136 746294057 588463475 904852997 453886512 422979062 423999906 698248652 866334902 870537518 127034714 875051708 960617245 235189740 771137520 800651635 689339818 723311325 856136129 601757013 752505104 491970150 458581848 504723521 680924238 705727285 81973906 797601267 93738716 515180034 307289499 516896643 393996415 997581309 100289947 584935950 153931035 346237208 174657287 358892997 552084026 175641808 900527371 155106367 720922637 93000670 223475279 951959744 181234948 638808665 409537176 21100536 606764230 803869292 509046358 949236284 134054149 234271505 446416741 335668551 527340902 758991744 598690028 569112417 …
Output: 9162064192

Example 2:

Input: 898 506742859 740461434 469248604 233244262 435556339 230962258 691242777 193816403 394910794 441020955 54578538 953977269 767071531 891986710 787050504 456144378 116637271 23285450 667506187 575034131 716852276 957422709 953647971 895281821 577528551 618830697 775360417 167477082 238987515 66128687 715878102 687173607 755902170 827090018 979413255 914505134 533829743 195271340 323551686 817986083 792263208 692204991 153604145 484021629 610837840 855709332 16713866 64535817 204733319 690627606 562878118 353569753 746561814 721702802 552464694 369642624 922138405 195676549 617714541 530463386 99092649 675473993 781991590 243487258 388614635 630351479 616412504 653982643 74689668 935895361 667189826 916994100 782154585 779977062 267411864 279273429 316018069 283879840 358998792 105630614 510…
Output: 8299949860

Example 3:

Input: 651 773444063 731489101 822637064 98989668 861048107 484410100 776729203 924102134 501446064 674454180 582579656 510926692 110103504 507436472 612310431 477661120 757414980 784929713 94154390 337114220 217910916 144601336 201233788 456368249 394214889 352631874 111855748 227103265 221112949 229036877 949041590 906819014 725695244 404299984 674404265 436970576 656470938 831648980 35402736 153778041 486584797 618339390 427215070 106386446 626552482 73372965 778740209 458996199 518957004 878746678 8820219 345208859 997518569 940886100 848600127 359375628 985631894 511444882 42713039 927898202 2176514 498043204 742614332 925594775 345532856 658043886 88748975 839899695 651653658 360690412 756734369 979215779 176390786 514082748 728448989 306381993 901274227 665047809 41505549 818756538 8776927…
Output: 5506566576

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Jaya's Ledger of beacons - MEDIUM Coding Problem | CodeTikki