CT60872

The Grand Facade at Briarthorn

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the forest village of Briarthorn opens only for a perfect tally of registers. Lysander means to find out. 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: 3892 216659532 605833323 434007622 593751226 828887373 65254814 700816556 168897476 219965622 84584801 737138697 349521402 11820172 879172697 42105533 802205763 10244712 826140550 14742352 285162449 247718335 638596262 699260981 946260544 111353410 912427733 559613105 919638141 225875963 465091990 619807996 472811589 255545580 944332550 623497032 771452549 244818644 475841193 11918872 778381214 521266036 965112744 647571459 421523567 639604212 76604112 795707964 523966217 935677932 50079146 877291822 757427282 8231186 583527110 507292151 291251953 139265082 783976510 645155502 213111455 423192402 59825443 313621198 134274568 90907146 72376577 118127193 607861512 390672856 550077751 889740779 997807217 92852982 683783935 92258151 766726693 319705898 321482573 620862447 725425370 539626116 2…
Output: 12467875524

Example 2:

Input: 2076 623077339 722655199 684800428 513083998 777867371 840447295 981802089 35292365 16049607 746801862 792256606 248983271 914133207 414525797 509173120 411907048 188903510 760904336 547127344 57764472 590068863 475110269 62055658 227025941 226970792 438371471 139498970 150048587 298476182 608958227 15018727 961599308 294862217 175820540 240085608 978691196 596767203 416755932 625555974 122211548 850142997 169842935 212784589 112206790 62967051 183349353 167698741 492266995 753433724 687033890 949480893 954128402 941248870 318143717 211011586 925342532 527383320 91993742 374095565 260307811 47176577 332594796 494993791 977684365 234356444 387379449 221267105 512474059 155935578 988775618 215003300 492967935 440279314 992443737 920471891 6502805 999258457 24229485 497442908 328914712 966524…
Output: 8063302907

Example 3:

Input: 378 341952345 905612209 30850289 200427526 241488177 508920510 482716442 517812358 430822429 825677957 929280700 515804617 626675784 186624782 428677305 236512256 828203722 802354943 238169639 807359051 582338340 103743881 119696706 549084305 699078785 170455373 971202775 597020063 254224760 172169856 842861220 984527927 338607513 957204668 46047028 244355803 692879150 958926246 698717015 948843227 410072542 432794255 659526515 303836252 176961705 573991584 637117520 477171198 359323403 147715664 198345124 733389800 613548387 450486588 832552627 818275876 753111720 137593275 737155049 592760887 699908357 241486119 905045887 165365411 725328528 316078831 763076979 576419839 561962464 797381213 638294177 912740884 626746813 464239762 190364286 482712942 821985431 122082921 852649052 48217488…
Output: 7691224023

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade at Briarthorn - MEDIUM Coding Problem | CodeTikki