CT58573

The Grapehollow Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Cora found an old ledger of beacons in the print shop attic at the terraced vines of Grapehollow. 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: 503 285845953 678215368 491167896 459503920 3890774 166180656 771975117 707099019 129319154 394578191 120717669 196356646 814547426 645663044 989278781 594220124 359576062 278640133 515783078 935246069 271817692 505062724 884263033 521906359 913017209 136438936 907096276 125847826 486074603 278266218 218102525 683753195 442603142 540814603 374431841 95423003 778555822 677183349 457373840 613461127 321143353 879075136 561286037 134733022 676803922 730215159 475430138 263869491 496364928 535702379 993247949 869968044 755360128 130115378 968897514 425898791 33505973 734942601 103056692 549114899 751585740 546597003 157826105 504836840 310916575 959432767 941068502 492102567 106564150 769690990 437904497 831804585 913401705 338365949 417738414 104181763 537574629 361046096 245835653 888977825 …
Output: 6127295430

Example 2:

Input: 819 383974763 28234841 819821514 765185650 479816366 759061317 81850653 588383208 439414549 162735217 210672315 823344310 732971287 599023658 339435645 176517909 867760659 323380271 301840105 102203380 451433339 142183217 812355125 42532436 708963364 584589222 728441340 612745184 238694925 117176904 774664779 862878348 771421046 783318959 324575526 747692910 956952790 617357093 698431925 883888740 599420337 163791304 324898695 679366813 269640809 309179299 760173213 295543875 210358745 253455726 562901266 753513180 438379196 602917254 363721974 758240924 877760821 164798308 90922095 773663128 390922140 457788826 40962478 879062560 802703935 557086666 966084161 926811963 666747120 806163735 857996100 505366456 464677321 539285073 998706291 850800090 87714237 743803240 96857329 641154500 534…
Output: 6609629610

Example 3:

Input: 1714 78105879 460782764 16675787 449572774 509217899 932654313 645123372 669139472 328815455 847405367 176189427 402306240 485388013 187769400 209629305 169388393 133393487 85038250 767299103 844005772 964441615 755092236 834378525 400714253 767194540 120395391 46279210 404074069 918793161 405231070 298805216 159325093 253379042 791348348 549784505 889983149 889242744 203229354 121956210 427280680 976850729 220882470 475612759 259471375 175192328 906764232 454297145 220311237 290547915 662366914 425127725 904260118 531216868 528968645 123414353 390279046 785273166 544941225 57349648 602380311 192037677 277536712 722366765 356374773 597526623 682615854 129579996 926963357 991898190 461226754 183130395 609761347 78225074 793071972 614302392 607641101 478299841 500019520 986500290 732543734 4…
Output: 6580536816

Constraints:

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

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