CT65250

The Grand Facade Beneath Rustwood

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the fox den of Rustwood as Smith unrolls the day's manifest of marks. The tally will decide the next shipment. 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: 1491 420905885 655939135 107957493 235879832 977663658 147460074 619691239 949032994 698547725 933053583 688030003 795514757 586397855 133781111 929646073 519229868 646456776 749271597 48824286 401106872 181543990 339132805 743908801 418160556 252558857 962352893 579027982 224075531 770056202 799325682 266181040 280166076 320684472 567677337 394429222 789430566 679731519 235628557 651099736 771929145 966365446 345006385 516193657 149579762 156285319 290814328 980843570 512294463 328206449 369145819 205378226 168918026 564710910 359262503 790816365 635269856 152780939 652768153 415362396 960648010 168749541 980342811 412295686 605931681 639640816 770129699 930639972 792566120 20509183 643402390 947369699 514366901 822915132 792989336 383655772 780055549 544460823 469512188 118835116 6838139…
Output: 7329408338

Example 2:

Input: 3491 285336200 773173780 521731594 814904997 502210250 375153471 260362727 458788125 499453117 467137408 106489717 195100211 986884657 830682353 119756576 588666030 481120386 335865996 19217418 474623130 389171282 66488516 457764435 428185355 347513389 408575123 72685568 513094022 474115764 496397761 846958241 880596076 760605200 737265141 880013496 562398547 902768761 356447795 197875846 160369345 132419169 366038089 376639803 606456375 833141391 373827385 743356065 591119167 166583443 353139232 362444627 453980454 85848116 330960414 59171731 789940795 64798101 778206561 368073321 824871485 47251261 616097650 259137113 256612609 320395782 89402843 77927154 962465922 728452876 958286630 637657516 234818089 263203463 505200822 734047635 177175474 176980305 501108984 640949441 324824029 6250…
Output: 9116384768

Example 3:

Input: 2739 344084668 902659944 447561501 587338667 656087327 739877083 555356058 75827868 534897734 206927886 699840684 161130244 26986738 625372951 456245728 555323609 411608694 983265773 519587230 123677527 805477593 726550476 192142910 981175469 309403609 791969530 923640246 180702247 563618279 96517840 182575628 838648555 662110252 945835089 808772516 85057634 691494618 146478733 409588680 261249843 733024103 208279510 662841348 261725054 52428804 100829293 660766021 283618075 419709490 726791061 269748950 947555845 410827871 132005918 471146936 673080672 339284364 38528468 673721783 125183069 294833001 307304703 488305058 806119084 127431476 488836383 504200293 760781147 377398029 308146269 301727571 230907072 521920376 769305392 695060449 767595585 399981527 153962901 463329283 701887370 1…
Output: 12493422180

Constraints:

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

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