CT64424

Xara Counts the beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the gristmill of Rye Hollow as Xara unrolls the day's manifest of beacons. The tally will decide the next shipment. 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: 3699 451177404 339524538 505234099 58894019 254510560 459836800 512158472 844527080 659226584 187142922 863651743 639943192 837058767 514290002 998110336 231162279 110461022 38671438 13490716 519826027 12965297 612089318 731258953 636988187 475841438 131839486 421621369 177883653 617132016 520516557 642387003 615106505 576317707 755987878 375631282 178792089 549728550 593966222 581512047 169726939 28402139 1478675 821995770 581601190 142875944 154161446 883147519 26504241 300845873 451788163 126288067 408601648 51867642 673896222 312498270 285564394 82345746 655442435 544210625 579571735 513211110 877054491 540194618 950263685 899617626 193569961 537143863 320368504 976285279 907777836 772556726 531668817 990354962 658432910 196991537 735905567 262296370 148982386 419364874 84404081 706570…
Output: 7888150860

Example 2:

Input: 299 667444277 196823127 832435509 196851269 770805699 656332892 288028785 39126016 894482507 94958001 981055710 884168193 469885535 350594948 259724952 185645409 137947864 218850591 448697989 513192430 265431079 232668249 222432934 716441769 602506727 922258843 624523619 890635150 14928701 555039755 639358991 683379695 942811195 299546685 750050537 516558862 158771349 413865353 353040747 318790681 252976961 771976015 924500377 537223635 114574747 249547312 255943545 503144102 895389133 720321223 257576887 597721226 391424567 438607699 321802377 96930500 360030711 644264267 542754166 897620057 890656523 334761769 512319996 855430064 748732512 593024053 802224739 756552818 107113509 445113022 598392761 426836562 697634237 601585251 675429047 137110488 361928182 770323110 150438704 570619561 …
Output: 6882065500

Example 3:

Input: 1383 441531521 915948602 185116923 572671435 63606194 631079807 247068113 186607957 239166351 584572138 720612232 231795026 125195060 744482931 385975001 776374059 893273549 869665424 239488198 477133396 722043394 407057228 601854396 82324487 426440284 755355984 260173263 368002358 33289034 579123479 971006201 606400821 324689083 196214533 616513259 924386910 511751222 238741037 709156928 302567901 164930116 658039285 154212465 112748329 328390882 655602338 792031668 800183092 249726181 663382422 886996637 907178244 437301481 796935259 9404701 252144370 845126683 972747828 12721817 145771070 813287185 887269090 352791239 556494620 5013374 638994572 5574832 404074684 458898404 571711773 34353476 973162545 829753360 745144884 111740042 938271209 687498784 36248022 675264039 132273691 7233895…
Output: 8328159410

Constraints:

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

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