CT58395

Lila's marks Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The log keeper Lila has been asked to decode the foreman's shorthand notes. On the desk lies a long table of marks readings. 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 209940860 179249786 718962488 338268879 220639322 282455369 820964276 580728988 682916571 54637524 127589932 820226862 666200462 757406818 673422475 465972215 821934247 848861755 604172364 128155173 76360852 210931453 72181137 965370894 669987142 348929994 983362949 750851701 393412091 870578788 107038563 671605374 609869798 123491189 226606392 373487031 536863322 920604295 958613382 442356871 974345576 526175427 362556229 241975363 849880245 596636190 553133842 161579487 232563661 10566705 869663257 361285781 658325307 27960714 966503014 697998059 695026734 807766869 470569260 142850868 181541234 998109053 634784688 831910532 899763825 710210188 407350437 482954860 729487803 791978353 421043503 9472696 124213185 857296617 244464161 864218325 864907228 759755724 487873543 383715298 38…
Output: 7435488475

Example 2:

Input: 1036 844176238 309038148 903583991 531163643 437166004 280945040 554946346 461700789 864483775 256161891 990097224 562650345 100153310 783979759 812306642 498160354 84179240 723382950 491689548 347035332 596901783 905526593 134540548 782231830 234188668 752035894 55594259 240000444 5455951 133897772 574101726 785523339 475815275 926848920 181218040 577878665 828018570 499734317 348962014 197843124 874199378 851128309 189687408 808460620 105456886 785021660 495996146 176789110 906183233 134971167 792564731 898251495 427379937 932966351 850516042 329898260 50690772 263313112 651796267 679799759 33042985 552478660 45046430 642759548 408052791 436092258 883052643 403995858 504915814 202565430 954767594 223346983 242354469 792696502 437567507 690947519 538602706 716596900 708171740 844288877 90…
Output: 8956164042

Example 3:

Input: 184 66752746 405942087 517018465 637063164 38999174 331260829 612393809 957163339 73381949 259351461 678484197 180232186 856126632 999558558 595712973 552014627 568637819 661162881 599714837 122135007 415916896 505370375 275460023 165652050 22297108 271763661 595258813 597845904 642484921 383580974 879694805 106879488 573173314 952908221 941837181 178964535 975360920 78317531 545822037 121455789 941440385 702541458 554074324 122628583 438869843 372477924 537842130 209254638 620487691 75162894 562418981 961867046 473201804 877138954 356414485 576417361 600678543 663438899 715144150 566153643 306694002 557930940 194054942 557297395 319717323 612852464 921491645 480950248 886423973 129162856 362229457 790483294 551300275 11647513 501553751 102913714 654564368 64676586 741874981 774037678 1570…
Output: 4504286956

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lila's marks Reckoning - MEDIUM Coding Problem | CodeTikki