CT62179

The Selene Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the moonlit lagoon of Selene, Rune records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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: 199 597235950 4419818 632238909 723513393 291065866 586891163 696530878 711320165 688481120 632343561 551879585 392271605 324336164 490926438 998151347 976902636 156762574 862759275 976740625 846247882 510872613 696455353 649615219 28003344 180806299 994980046 274994825 717275017 433121332 685700804 336294460 818428149 916938618 671127706 436518324 983814028 664170186 782137049 612419233 527811887 796091275 793314548 907438995 128727812 590731160 727471529 119097012 816111798 990683390 12970173 792770072 367275085 107213903 776253896 516313441 856517391 637117790 323084379 902932193 746098544 146476481 133798165 730714972 350786643 142339426 177315848 477813400 709521193 184824999 305024736 631778690 371686229 341761444 426513893 538988022 552388444 851422007 586488834 279991599 280697441 …
Output: 5410543290

Example 2:

Input: 1547 775120229 674385053 378013337 163131080 269553592 813128192 39938392 231227064 81699579 877994951 317552424 64912372 95982679 103909821 366902552 988483559 329198649 895198523 155292668 783397687 395294110 489960595 757489227 13349229 929230799 227395190 229804776 971099922 515677672 325729507 735966384 232321564 752967635 995087578 637504397 652952966 301270661 633660744 798397120 426736374 657738820 582685879 965165739 423828592 245653617 5367735 625327815 723451451 979142241 205647490 414845715 42357209 672752471 209309306 122331206 432758455 398795229 865314199 406446068 327222874 847948967 352207957 809418678 959577589 70108520 824821589 750832740 903777291 79129938 24466751 803554538 824506834 309518124 504750922 326376683 923633135 164041194 205556432 88855483 354663110 9292274…
Output: 9106580730

Example 3:

Input: 3027 272641086 972425316 58020940 650240311 643319111 307378032 33833635 325667425 282587036 119482154 463667627 661083843 523768032 105750493 804683899 698804368 820285171 945348743 579608874 263744339 509113488 744502754 395512777 810401467 233513753 323255686 978297378 400431412 231320399 315816797 49125554 7236140 955101461 654345554 96689479 807016277 875849959 73219268 309223640 558221182 23106133 510939138 807395434 173995838 807770049 707251694 664069710 121704903 524445093 29856499 560341641 209809113 705841289 434007024 729979255 591099837 68017842 917609192 966293265 889005709 623997220 349759014 395632355 268950272 919051408 98656817 772376573 499041440 240975846 18174900 203737934 647420838 610053928 296493407 617726789 96016400 760872885 442681608 254031785 692773184 55905255…
Output: 8191796275

Constraints:

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

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