CT59652

Xara's beacons Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the mountain city of Highreach, Xara the quartermaster keeps careful count of the beacons. outscore the rival chapter, every figure matters. 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: 1232 770693403 775399737 483787480 684693683 633451749 639330993 196770624 395362757 472787489 200064987 875624706 22326419 755674699 938467279 818565461 62455775 2267597 426365320 297776216 337148065 757327666 849505056 506954353 215355359 112444417 699407718 691603572 494296377 744173890 616144293 240443584 922575085 889894910 922504968 781544705 758138133 558346720 899869657 72366384 278793402 674761609 116476770 62515153 404939938 589558806 884992464 371768868 356714985 132957883 790028588 801427096 535651248 96276908 216723801 150762535 268332634 51061499 23958697 40706483 940184800 882009468 343888393 258708212 495352219 718193820 419300256 67679277 76845255 692524462 511610799 158080724 751639035 777793134 456011352 933259064 946885226 182357030 401864360 429624603 759008410 8189991…
Output: 7246664205

Example 2:

Input: 1172 435045044 988551792 625877070 634044160 571633717 291672555 89393965 167372831 231881007 108857265 200114486 924090410 688125927 813654215 297587706 74295653 112892482 586852708 778733993 194930444 341285820 891057411 572162029 124731791 829629446 746343207 110955937 489376321 430184313 119863535 137586116 480540349 934771695 271478545 235441127 743059672 898786681 344964838 593906830 180210862 394236051 522495313 906416743 418536572 241422120 136112864 925856903 596130811 986698739 628628021 702758094 328606314 766219557 690025030 301841512 492403250 126110424 72777828 206101622 926636281 751837752 526490406 735332660 885025077 461208731 643939512 904021707 906402907 272768883 593855516 793090196 795546802 476797926 980481960 855536639 604485036 886890456 18060084 486597766 864888595…
Output: 7122467662

Example 3:

Input: 2301 185622754 772745605 781010491 532884414 887164592 501937750 553232764 961238152 34861090 965118961 750015536 647159992 524064474 452441185 223323974 661352104 810440243 955012827 804232877 53839288 344004465 182201257 298722910 245523378 168453048 66374196 166278060 298677821 20856403 888994006 309407873 449414482 881109270 110810352 255259372 703455847 296473627 354487017 86883911 281198497 332013626 22725612 647184154 393843120 978823993 719588307 109706875 70198191 264416145 387142859 735103033 289200709 759861928 226637840 545980255 615487863 391949073 46105836 561745680 685345160 767686068 135447318 237707620 704765909 448530726 698575459 164545437 418115170 739639461 786401645 431445147 2467605 7668230 913196019 278410539 284917040 532720567 627870132 259624938 955112590 3029093…
Output: 7343296353

Constraints:

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

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