CT62195

The Grand Facade Beneath Mirrormere

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Sara inherited the loom house at the lakeside town of Mirrormere along with its curious bookkeeping system for ledgers. Time to make sense of it. 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: 2133 357528737 556679423 216190905 108960520 288038769 35424565 312618691 347915568 54562230 971478739 694912823 928884230 795973104 798896737 902529978 11608620 609959272 381132587 806992187 644094856 581881244 37983255 965477142 602765679 81929071 851748639 723691938 87428493 286617133 459867698 125456708 714921957 356551217 488894530 130677375 131439093 237848751 598308576 376880467 569131568 850013458 18579193 670089303 530542790 836364453 789577024 55651859 242005088 74412748 322688292 182796703 13629821 285257743 859429521 87922493 961153979 843725183 494896823 579580789 334615243 21988292 931184556 523711563 644764299 678149826 254007583 525883847 394526148 182605489 9628914 498456215 144596429 92749819 914063680 199966330 359552564 145745393 742421147 513770185 973230808 154293796 …
Output: 8051061968

Example 2:

Input: 3619 383336203 997840225 989510789 28621166 471749906 296092072 391788604 224665190 473086485 785116858 645623005 707892890 718224581 509766906 941503993 479385544 249622055 224577618 750465521 844797428 799212557 145462585 774195202 803188204 487251048 806644583 348243984 643341623 41230271 384144055 624186225 461122174 156504134 781897020 712248281 461401803 322194392 651956834 474757434 354781336 717013418 832454006 869258500 263059564 287578033 491346436 128729734 301498973 227614539 704270094 280137943 200047698 220308023 888853246 860223300 794294273 51413589 670446286 415987659 493610674 689583907 13663622 947638208 189483923 698589312 263938579 850163675 926553298 933392453 490573966 654032616 480536680 74700361 496897431 262138773 453433812 819034814 926835064 293914678 565915663 …
Output: 8256256400

Example 3:

Input: 2416 64084801 615994309 368831930 963610700 427265584 68572903 349447884 690586058 563909252 537626729 289391569 875040778 24138358 465749802 962449996 128024010 859297751 435647180 524963358 501063055 768577042 593972398 600610972 17096755 253956927 877066547 645602472 563551498 938522342 417950508 484524858 131724868 828222531 640980419 728314210 545167535 528354588 413041815 90343215 321005139 627896898 110521837 368701700 736252985 156117749 190423667 316017950 192086610 132149218 697359202 390137507 381385604 86509118 450907862 192153598 123572671 63427515 617476232 667113014 880801331 344699520 922698587 762551018 227338990 137105097 498850121 542494679 841675135 954935878 704688269 726440061 942479983 930386095 30465773 713700558 711299222 15941108 915703340 413126807 587226249 1666…
Output: 10544413070

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.