CT61514

The Grand Facade of Goldmeadow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the trading post of Goldmeadow opens only for a perfect tally of ledgers. Innkeeper 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: 1867 982839531 45355047 224073776 332432484 504630037 539401868 4099190 192501492 322093254 601204535 515070272 875938519 507042764 527091350 18615048 918395642 152873753 846154339 591472993 471406555 689887286 377090085 759794248 26526698 620804163 612221698 146559297 637159333 242283359 246862846 464315868 50030014 848669966 414262053 646579336 177995840 813418223 499081291 422868414 313756228 409620853 751385219 853139398 552696926 737433148 262632375 354962084 437240189 135742007 245239393 800139547 126352233 284351205 719890133 681918193 33786806 194059346 626857139 475449433 108118895 840040171 16429421 285701125 150865180 627309430 302212992 119256093 534025950 813002123 36726502 261275863 679069247 850799993 176772356 256699572 786241764 418342091 536985831 194949539 10279850 65208…
Output: 10623411120

Example 2:

Input: 2534 459050061 692881030 212033471 956179872 176609393 68060790 818929945 259839631 457783586 682424193 357894828 952820833 467272076 66778939 273682160 782847069 338855134 947633990 780658118 731019613 496698226 728651446 378015472 877996703 375652893 287027478 724824670 82557088 944192297 933688527 449340253 779670768 82073276 991223724 230047922 860529238 965307149 662428548 344803418 786260755 453796744 248097507 54036140 1495729 575305605 635957395 828984767 210079601 554458809 440669966 483209876 631455199 844995434 735709274 833835029 10889567 101586088 157069989 182957247 857384722 556428550 572041012 116323743 455399874 531321250 615010780 309600709 676050630 625450847 101833630 256975036 536132533 309711112 237624779 621202261 446436367 880856917 144600545 649833884 159914509 324…
Output: 8750784798

Example 3:

Input: 2511 668949211 922641487 455567578 620659525 192349338 901542226 390800569 545930528 842574103 582746787 342559641 955300031 284141756 756927852 73493243 333402849 606107816 982167214 128826263 140821350 103558245 375873812 502790292 341809905 797252701 579891793 325088428 538561850 607943566 277707539 427522558 890402365 318430110 365443587 135074928 69462706 316711131 442180850 458170156 87160086 761387897 272815701 348612925 344579723 689154271 658642235 77384103 524199163 567780437 434231775 320939911 686735785 489244112 306811132 129567463 517630382 491171640 307784859 149394620 293503087 64955542 508800606 405157133 635492170 663430076 94154821 890884592 611448596 433166582 935913833 103308998 799677112 911624446 321485378 397723683 253033763 857339855 165169432 551951977 421786245 3…
Output: 7617389438

Constraints:

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

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