CT61992

The Grand Facade at Fungaldeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the mushroom groves of Fungaldeep. Miller spreads the beacons records across the table and picks up a sharp pencil. 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: 1826 641256113 913272500 892064384 926170538 314633755 716179029 123012375 93756022 889772541 441990290 945587357 238593639 167603483 96149461 292425668 16885262 915833704 201458054 734312641 290800664 178307632 647785609 200264263 987013198 344936023 681970132 39177335 80534422 505125969 500317945 917539593 282403062 764059385 941822811 343879091 115196290 947697233 734745630 841220420 7577681 21469901 786393001 549593335 176825089 977777038 937079245 705135385 357028766 547431158 543932548 913420351 10662273 53283849 942450842 151729543 862782203 186830986 839637855 142251118 322411202 751791210 445964765 448317409 329785150 625147521 748012160 619522223 357284864 210007520 850964239 214813579 563245747 79617224 521649409 6448542 974536586 291255442 474031416 18725343 285689158 850343522…
Output: 6982969824

Example 2:

Input: 258 440038600 277308914 412265295 48776820 263336604 553512636 825999808 854934559 61886961 993738186 359967776 722533909 583442663 568246230 353419990 556110903 958248327 387784714 580732348 164351007 948709877 474427067 802260645 736581066 911722565 141239237 55695205 432728695 317152358 980212686 427363460 380169896 607742615 601158988 271903482 845905486 354018250 254103323 641532627 923376557 937289986 419695317 44191437 358065857 256532601 138735615 759258395 597377933 844787325 433047548 196978398 317956589 625219922 576550984 9999227 49382877 524619114 935164716 10556120 916051976 812513221 260457960 652557965 32975324 667923936 742278884 981347261 50620626 36661406 973778211 695060490 738983311 219195079 439447860 106247342 882402762 471926051 659364108 230860866 680704022 7326969…
Output: 6467773195

Example 3:

Input: 2347 191957763 183738102 50673183 226002817 15145314 273209137 852410284 515463039 369793237 655471923 277706166 66762375 179687424 273438151 493798129 976787008 185091943 313826754 148526136 278620181 104621671 179030241 278143953 209544412 469037439 96056613 420526845 289204082 216919578 673068854 299846176 10354451 5321966 533448851 958479652 445069085 417705179 894723793 89948555 454622834 812227869 585453987 204320446 658274133 690653746 83908458 777374485 519131309 380746069 49152702 424083587 263836473 663968058 740872130 624654535 318915049 645891447 497534702 235048765 597416308 336493073 132193821 942306422 188474071 315928760 109871384 153399426 606532965 223041859 548711889 206493527 587846787 158838447 448254088 50119512 350793218 462508082 623678486 101874201 517441954 625568…
Output: 9442427824

Constraints:

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

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