CT59674

The Silkmead Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the mulberry rows of Silkmead opens only for a perfect tally of marks. Nils 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: 25 841221611 263709669 572410301 332174136 599362743 531782264 122450857 2515800 497556113 419619992 436618162 147540302 695185213 510715383 179179669 848999370 18539943 231235259 672872924 384156288 238769193 485787060 821135905 558196440 226400846
Output: 1811206768

Example 2:

Input: 2413 447788532 295555036 588355699 527411421 488309412 75326602 577029839 10491123 826012479 226257498 392479086 318844790 3156080 539701043 624213568 222071980 98320704 72146676 77803404 179324524 242303950 736601516 132099065 540881899 452486056 431395469 575932643 72789977 842810247 747744686 600732024 292979047 159812044 709263973 486798368 170573244 930738622 639294409 172387001 252895508 288035499 605700652 940135229 256870301 626312431 884749241 39232801 277589436 640511346 185393187 569570079 409999406 882956123 247057912 808133442 814021434 645451426 514566385 66510421 277650380 729403741 330230754 2056954 398509648 786668209 597054668 259545682 71338741 632937782 926813936 58551875 743153863 753729656 669752272 367389716 285115652 68513977 262990904 191587479 877680219 51094647 4…
Output: 8638693406

Example 3:

Input: 2328 235460556 294855723 936894972 472287913 254736874 774932573 770382384 554176735 404549962 205236060 562268384 807365450 665457884 623453722 979883451 76676709 719254697 564912777 258019628 415039469 921077572 966076780 827282928 799197069 1159857 3044498 751337979 519438822 623415977 563057865 153469488 496868417 513439845 858811460 300372955 179157960 235465595 528039836 849872691 72462450 13584935 473167211 467216231 350358042 825551388 646439674 66554476 466890246 661612036 311806290 349670704 625520880 771940860 521476556 698515739 970448209 226728026 304605164 751141032 406282445 71096157 63139366 137336787 589236205 776495786 759353881 711957753 756716712 952656627 623469937 23839859 410972713 342753330 440561504 233958564 300797600 988932248 162434228 210339083 557541555 851878…
Output: 7263260016

Constraints:

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

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