CT58302

Iris's Hidden beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Iris runs the counting house at the lantern lake of Firefly Mere. Today the books show a list of beacons, and the numbers must be worked out before sundown. 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: 614 248074283 533753819 351984560 939824218 243607231 763656026 654660750 356419382 104124983 754357908 608354130 894567832 162119170 87315326 966231415 971944783 255505298 50846147 500109855 478966086 443766558 125840829 108810619 135125981 300778179 61616055 119369301 2014350 311073950 960113331 764396296 224505465 132249339 386498336 915017959 636898024 716165301 359690292 727627514 233806370 442499025 607461752 27707158 948245710 33741812 821535746 179904397 739795638 937863752 269290455 941933680 304460215 607898562 750078466 483053265 898859873 256299381 502514735 525786587 62662353 693779413 304181640 773637715 508968663 327155559 876688116 332233864 825989752 452305208 838064521 391627409 359759930 369392627 61215969 322093035 282260048 935496063 536483754 556675586 137795025 80139…
Output: 8507994724

Example 2:

Input: 289 728757653 711171258 71518871 990769564 800199574 370683454 118284502 800374441 601909597 969865201 238742640 904852873 175248350 162515769 586718937 410493629 77584685 704968534 346787652 60683359 33515432 50745649 611981256 9023391 695109965 283746931 387065250 555130856 486750882 299847682 175618033 641574099 641901351 267658139 490430673 855645673 272322575 931759302 577865258 829255048 574432008 183067088 348921381 306376275 812862279 877239758 545824084 473030363 785196081 417247050 794390409 237824181 615849024 951923297 637995570 62045658 18338853 698997420 140494874 536845865 153975856 565743377 20475752 136781507 368096450 895639765 174959952 458304377 677023579 994105265 576989591 765666951 210616287 663589792 247618913 720536198 804346175 277150639 944000222 486415331 633593…
Output: 6297679020

Example 3:

Input: 1367 557469041 911054145 441462067 969157571 700028125 953812529 830991034 432730993 756720876 481501000 874477721 936283143 144627442 859144822 216814285 215858788 550565277 39741777 612570786 31638266 559669348 148396470 697096855 454142958 969733408 64750525 342185282 755995541 287257696 886022063 598077130 467010528 45577025 731301039 296228990 892068953 726603065 59945965 603856076 25392107 733664833 950940971 519689926 497259665 441941433 698528242 325526986 927886622 65781024 573456033 571407588 451889359 129968993 953039067 631621325 284423565 957445391 904186054 162446543 401704140 687450495 408582718 356207266 235564912 382552157 553745103 324139279 170951157 527979883 726993885 387472675 301433988 915687247 73777260 408752212 4461896 332543705 562680454 443144839 777141265 50990…
Output: 6100121696

Constraints:

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

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