CT63554

Vera and the Jasper beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the fjord village of Deepwater, Vera studies rows of beacons entries. One clean number will settle the guild's oldest argument. 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: 631 929737664 788861128 731090716 951282610 725434302 926898037 817464429 315530627 366550980 286005682 701617389 248040120 767317487 483889509 75444305 314949840 309700328 931734241 887858307 189636031 737865403 40781898 285422391 540834832 253003241 676791472 300562911 948093474 560987244 60919461 80985952 494437523 380339109 584941059 423340004 45802701 904790527 616369044 756122765 272975066 176401890 226567985 529024008 686975758 875859386 911575635 952917379 938445964 858041102 543736481 14593672 802804868 287840954 371682710 144938860 254413614 674361361 170145158 737538523 502929764 533383527 471553132 694023433 473425380 291663483 323911466 60801056 3954454 309570551 839894993 434272615 130455622 691141971 930530631 961095800 590855242 474888660 194371831 676493571 745272186 88387…
Output: 9010632263

Example 2:

Input: 938 984651672 397711683 843853036 119234779 57232800 404989187 922219570 160851140 975125342 53152431 628670372 663873759 578943595 116608658 394829826 109081089 330595794 407725487 703268032 46770137 924095214 609467591 586828415 78211886 611455112 558594400 24203165 585774001 254139520 312675329 359846200 758055386 351492095 847264076 955516576 915828736 841405156 193206837 269962302 313810265 590792124 373811407 343806732 202054067 762851349 775030949 44831078 494505387 319236636 362458919 766013049 816010695 399869663 59438515 212520742 173521855 128279315 919436268 626793504 916203152 895939767 488768672 398676464 700288953 745001958 223009637 480591600 660463684 85473953 172372368 867616440 473744024 567700843 336667311 244025495 299821025 584376228 460378880 279996634 354012096 4265…
Output: 6708301265

Example 3:

Input: 1935 120533229 447438940 558902217 607000618 340671732 295915714 781913211 79306794 376175174 597381321 461408049 848261243 572511019 552666812 271268598 854652663 642361502 252698553 452657815 375347726 681935824 774460316 109194994 484480423 761816594 638500704 954985478 91893623 597947794 21627751 776059052 843740230 11374471 944638863 963868162 210585267 148980545 945328841 693761289 430795554 175643977 166164687 972939882 387710050 834541074 302013314 619971924 956517439 329762652 86347756 286085042 601143321 536476766 385842450 419712529 491590462 58311775 762587606 325527634 981411696 390739559 915811904 378874096 306366172 737669189 534705283 971704753 256622046 867102216 233523025 629494367 611679337 466606339 715018314 654906263 879219176 265379301 871321772 71791089 240920009 19…
Output: 9190698624

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.