CT61257

Innkeeper's signals Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Innkeeper found an old ledger of signals in the mill attic at the singing sands of Echo Dunes. The margin notes pose a precise question. 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: 415 655636315 476826401 229120945 170113 83480686 357948773 980454055 996793942 877005312 762295210 585612796 963400621 219842751 307304163 617731798 276195558 307144392 95000046 235071557 937736599 397585522 403617415 623043597 587426746 36324768 165424955 387168175 108063617 331511882 946368652 684015059 568059990 28827080 575904968 653800002 281753135 813536290 572755874 332098855 953948701 419556098 2263271 374584690 502175348 235954284 987536263 717112575 716442119 594382671 59804487 345196526 207751309 424691298 576323907 204211673 463948898 977095036 182917314 244370826 849676453 390981429 468174122 147456139 514700701 882356768 887786166 71576537 457658364 23914930 734669581 546932196 606017364 40214850 318938319 904576749 325410893 819878800 794851242 239076305 134394370 327280413…
Output: 5243385758

Example 2:

Input: 365 461093398 265293579 72309451 326408031 576747529 825813208 767426219 281866023 453136842 575631876 449584076 541629030 472556296 859310084 850762823 221959150 954623971 544638841 698982169 227393920 383909759 342355589 710002583 204466305 203474160 608889243 20758232 545000267 139928959 500884370 495510929 849421882 415459319 312986176 176784149 395188356 488073378 635731850 310208665 184496657 523338239 943411961 699136790 596726583 741987347 664679900 388649544 215670192 160498786 845882478 956235686 59220889 384567720 940295429 197104333 621487847 943469187 866315733 217883404 990213734 321184259 59270610 256888386 322496567 907116263 713823956 598279623 275270041 598456869 323830493 553802004 303174830 562688758 910982956 236960882 895660450 483384632 813073933 136502215 333069284 …
Output: 8384280856

Example 3:

Input: 673 504697234 467155229 584691691 447043016 210285080 45316001 853302881 319731023 83951420 42349437 724158824 333287787 3494093 719533937 606808941 644785780 125157129 294584161 151970197 550253725 970757883 350070030 537286486 220417145 224668382 367968422 337879429 993552768 249276574 173385475 653623144 540239713 494117351 231231533 285300834 771001044 997502524 841333480 741873007 967586709 792762859 58326864 789828684 396438437 799220657 930782791 741057481 150844221 380308836 382409884 645167950 261072837 255104878 482592690 161852590 255109126 874593796 685133355 843580949 944115123 680121330 50145498 701541636 110441201 783831238 323118615 550320534 936220403 880971408 641113962 512562180 663831642 627648221 867015737 980700507 281624742 658352901 484878880 147650615 142891362 437…
Output: 8648036086

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Innkeeper's signals Reckoning - MEDIUM Coding Problem | CodeTikki