CT58119

The marks at Greystone

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the shale slopes of Greystone; Nila weighs the day's marks manifests and starts the calculations. 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: 3705 934657232 337799767 875538242 916750516 677856832 90486454 478162199 196388582 188239199 109181196 980345257 672339421 58574826 917093313 746909055 809376168 773741147 964929839 176126395 281659835 432856857 485509899 854556913 713143659 523675256 26675976 616733647 201399987 196365232 8988294 263960390 894416907 846134596 495209892 198610648 680572881 750762829 27914507 369769054 207376499 516043271 431102619 932966452 867111479 744587262 775944881 930128998 174640960 813056166 671439496 335829321 100791076 957450961 684758464 766390234 762818727 31141036 879731436 792886954 240989019 456051441 114323042 144896093 737102590 316311625 779193915 887143399 660384126 606368875 330703440 594149568 363886632 109162883 660363921 811957187 801546165 798393550 577358611 546715923 180145851 92…
Output: 8241811740

Example 2:

Input: 1079 502010310 603563301 272321150 586113950 520488988 962172930 316500479 406211663 159856216 66168246 233868647 381996318 208722547 166267986 328218183 252565506 919884333 440754066 702154140 752974202 247730859 702751230 462599827 657189491 40805362 951195536 979975703 45334539 913219630 450440898 933615100 370851507 428639318 27192884 657255432 636394701 503602579 877750575 79454652 673769255 601753429 394735628 455759823 233415299 953244186 471597079 960536478 868639937 747536776 510998907 274801744 731770801 476998037 414456610 448989219 899407424 637084590 229423323 37615866 998332792 625189974 913381702 25463393 981761478 85806892 362741052 496781065 435250073 431466886 814995429 878113182 437380822 67369867 620721480 88005692 964936262 168422129 3678179 788710552 526908130 7836315…
Output: 8175217267

Example 3:

Input: 3606 174910491 600174127 979773962 270138695 841677399 293036226 449847455 127671661 817453472 429706408 243977818 187678331 697062205 644062630 342288396 425905709 366488597 701191122 912157550 97027465 650229947 594714140 388618170 183471142 858866622 756739632 461514573 405497878 641533795 714199822 712740794 650883177 676516694 132471029 280209933 913815031 294713053 878285410 231173174 668355842 959927200 218103022 765354407 974929819 522988437 541138247 802474632 510067770 427010771 690185634 861934601 169977229 126323124 833827118 418353107 653907365 686656627 215461312 287689355 27130639 668900199 102516298 238602112 118761990 814354820 487593143 595752878 873590386 536035905 51626109 966345283 766780912 826225994 414812199 568425847 236475378 752607516 371076056 19976806 356283602…
Output: 8105909952

Constraints:

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

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