CT64836

Opal and the Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the shipyard of Keelwind close for winter, Opal must finish the beacons ledger - one figure at a time. 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: 1115 720433124 799848031 855788985 50755454 404066780 235456392 391177843 39280015 614465488 857285258 122076879 421120566 209641546 150410666 316169765 298636800 860612203 522823236 646262780 120164991 293946313 373335033 578411302 404766202 153401178 537035114 833409797 226707997 120349304 11155464 125666195 584590390 196125017 43416385 701539574 441053320 174636644 299857708 418407463 837766960 747826315 954235043 94796738 583695522 32870737 717558018 491417296 620967283 550081104 713702724 741235216 104558689 741794109 522779293 243477444 514000168 893037240 502432964 38953159 742064920 74939083 983379475 206308344 571357999 466318223 626215765 710665390 570256033 985745903 558653597 734427445 520172323 573390545 455029463 82118545 202179976 558790453 745317973 544087750 244922287 8123…
Output: 7918698568

Example 2:

Input: 917 389816437 563819140 661554416 464642908 38487734 921446311 870050342 82657308 816487171 252323850 110509013 300060516 591823410 932870750 603801971 392470921 46366087 74235064 970542931 299521674 849991584 984299436 513511242 175564360 916837390 849901184 560815263 404286051 718387071 451078516 515239456 848134508 247914454 259138373 505267853 941202860 176088356 945421235 462105294 620443503 820992137 222798185 966525159 938901541 179179816 416583491 52752487 408379387 737546661 248052504 248374391 352042750 253180156 837294926 26616633 229524335 701529287 735913395 185376190 631649498 504616947 877369790 59576900 703425244 632820756 770569275 899170483 266845154 449740244 230023589 154928619 437511584 456797381 24777576 841596795 226912534 172377358 136500930 589231458 788294105 3872…
Output: 9193005030

Example 3:

Input: 1726 413965392 458199937 350773127 951281120 867233621 413171814 585554357 883926412 28655412 345363114 180314289 832592221 707822011 721656473 699487657 448421895 274047577 552619137 860589336 222091526 348161996 653855176 943113429 787318454 690835385 493391970 285881866 422081086 785136328 478403903 266115881 144496355 374326271 215061665 271871336 836689610 789725890 709854609 197821946 653469851 547824525 632129116 418658181 544977422 340202120 848356543 601186661 971007561 928719671 907040890 38170855 37834203 95952766 919272307 738349771 500895491 930392471 268798957 380723811 192001871 945712938 447898946 414830003 911343441 839335640 436788704 370293871 378777466 195895057 791174428 242592088 342709336 847414320 875745592 794783296 580244448 972014588 11062949 663019973 378011562 …
Output: 7468756431

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Opal and the Grand Facade - MEDIUM Coding Problem | CodeTikki