CT57262

The beacons at Longlegs

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the heron rookery of Longlegs, Clerk records each beacons in a worn leather ledger. The guild wants answers, not guesses. 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: 2755 841480650 945924506 741000659 218034256 345989800 540375456 490782846 834328810 551567145 824591012 121950240 620192052 609342098 267006752 85745802 789623573 816551213 921582977 101497796 413958227 664911943 966060667 530022137 847222033 391808081 50361598 575997135 636853053 23211491 237923375 872274650 350020114 961040209 919284796 642528725 562526767 231970794 763690931 927099953 748285032 796913227 618402580 778531958 499135384 747343661 115801109 593333801 929347278 242957792 849944147 157798797 847259531 702536661 722871992 845295252 942286497 167112303 819623575 171183329 286720185 212595952 631066454 301089952 811908323 897775587 437188433 883275033 430891114 644063045 474163629 9233241 42306819 602917932 452783365 331835686 576569011 985962515 933307567 860300727 470876111 1…
Output: 8417404944

Example 2:

Input: 1203 126330718 271375035 788549684 365927601 90673393 710819890 737941811 9695068 814141739 138444197 117614677 847202461 413306988 178051025 982857427 933166336 643109449 11859339 264956419 471898159 386553274 289699131 931994869 159490073 634646684 853105447 362334015 154498901 579250060 165211511 81228415 25169164 134225775 147170634 46589020 918708216 280878545 500678708 678362166 618352057 429736371 759213363 789827126 850725741 121219805 151438335 736240182 408589773 493604888 603909843 148750431 658972170 517520510 958567123 494216574 821780435 726405061 137080428 851633522 56485126 956416869 428548630 916925245 437310120 694871293 651134658 724207789 119134889 114044947 722018817 28387443 978835581 172561155 824136758 604380421 441036836 720387391 981299557 477628424 65072756 33228…
Output: 9280333248

Example 3:

Input: 3428 968856786 713201661 839315446 146319842 810927733 144367780 539985819 630144209 232417098 517990311 53980248 624031464 277630339 663538746 234448742 587627931 103887415 188746260 403286374 96980992 731159338 873206785 574666357 149531648 542633979 562979241 615781614 751788549 798119204 585868729 992115655 429538075 116325556 955319517 425260685 677748731 791031370 552240473 295411523 714413132 741283250 960120506 565778389 192720686 560675864 83072608 583647377 563678392 522060582 808470858 818639443 492483836 712731589 284060603 961133601 773500766 243422693 317331622 588982935 935696427 182520884 136012544 467428033 264949967 842639764 147446583 348309321 431311225 689705984 962826487 425330579 252134846 157616961 471296309 628586794 330254286 927001579 655024238 816121834 33557760…
Output: 9437012321

Constraints:

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

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