CT59438

The Starlit Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the rook towers of Chessfield. Xavi spreads the ledgers records across the table and picks up a sharp pencil. 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: 2275 298868556 396712213 38824073 527457689 239237110 222720561 785016907 372210695 195769019 816462163 446926154 666771117 411535300 712466110 52721451 752730674 269277174 948246701 290964223 340054457 383359086 729908328 148143576 651157732 152118793 265500235 640191668 711510733 113647174 781421340 276792026 585565516 129492687 990053144 77998158 424984389 787152292 528657399 355283842 586804648 696914754 958624394 42484133 509061010 392241231 146037460 751132185 144004959 318456743 245181061 477506969 37799636 203482271 276024646 141118427 214493021 877041427 817028411 678421496 167470324 157232902 992153247 126489806 51788935 681683358 814774676 251178774 672093301 55205248 984826566 868492275 570036079 120792486 898838443 975145809 784660114 240429054 198076414 383412321 979362813 57…
Output: 11729902146

Example 2:

Input: 1437 576465050 383063304 784272111 547250995 307237877 526420067 315206128 824219460 115103199 310128318 102066327 873844083 631654837 561224995 565530735 695787963 79993837 537216568 616299938 178072687 8964391 837815264 768861579 626295834 750364112 984286419 636473179 313124858 776417482 356803398 769350216 848425599 424620448 994925373 709918644 889221937 546864461 701367756 841192237 770278871 314330465 934803879 923074749 532843137 910936388 397016207 976443151 135890226 370941357 542624217 462236023 970643364 246658196 286501960 615834743 384881173 872806128 775215119 295009491 309794775 962092000 30658795 321354401 364284009 727695575 87229364 111836176 868672845 980870475 547504205 39907661 998230173 436713363 183012422 251386998 963973524 937262084 685615120 562610694 698245825 3…
Output: 8141246308

Example 3:

Input: 1195 904857404 412437054 115814162 565234236 341047432 648061960 737643368 93246279 369692154 782820025 866286769 526235866 890127245 429543469 455128576 123381249 358475040 237665511 147004257 879172715 997844281 197570045 96519798 147093959 767358822 196448206 794075553 907415860 467863429 713706488 962780471 780690129 948035701 378330480 926631325 734337743 338378870 384395128 822475885 250463942 902049399 613727022 663508209 505155331 648343722 896731102 849032118 968288300 706118139 128833501 864766994 560624260 468343970 735687601 392699175 473369078 746857627 24525221 871146624 706032795 919970581 472037733 595861078 271150677 828436186 497897970 458061688 171879000 319370283 223768281 507786198 831184946 871137108 219025052 260977542 282939565 983090762 344595433 735619389 80019128…
Output: 5760670666

Constraints:

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

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