CT64771

The Wild beacons of Nora

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Nora inherited the aviary at the cotton rows of Whitewick along with its curious bookkeeping system for beacons. Time to make sense of it. 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: 1664 53811935 905267921 295462560 920447761 775568395 335745149 429287701 584121685 395351631 343393162 989697607 945386075 85712961 338979337 354212980 123321227 764343371 59869922 509783030 73314135 491201442 231238693 625305132 916088695 810156442 395183810 463436240 704747430 707193353 626209613 221569104 367141032 572865001 369520564 251796834 182827574 434487490 839670132 463129439 354121306 414885440 551907191 881715083 412337777 587095061 419816088 54542469 110154187 568875960 725981900 854848855 404717000 808185260 750803175 521518313 663090250 657713947 776066366 219257916 797226061 437794646 447973724 893632588 294699803 949062713 566294384 999837300 772249014 323478034 244441957 462108349 128975950 122218941 178837425 501520245 502390626 786197612 615804272 231434485 697417948 …
Output: 7245415170

Example 2:

Input: 43 445741934 336549574 220701726 390070472 270153197 49020053 672540120 22440653 74023790 263361441 999620776 500548612 97002466 786025689 552466774 996362637 335091868 524888579 469300371 324825774 974186762 515198676 355676755 900868939 311388666 498853921 211801031 479881904 762271511 924990205 84748867 714639190 343838647 762902180 240478741 196706939 875284718 444424844 695297734 721771413 458737109 760391573 298113142
Output: 4048052658

Example 3:

Input: 1714 130921149 35256335 93817481 578313814 130190724 181353986 432291238 424215182 360863931 975589313 32906276 985264942 325166461 455720599 255746717 855869549 857365577 870383165 174722213 773464440 114607054 593225319 995298174 195439888 676913913 876096796 181079984 277473632 288643352 44027084 835483945 773585781 207783107 492429869 240889618 789944780 907324746 41646376 160401675 870943216 737356741 156485154 392914306 447155323 626563131 127828359 790489392 990417116 410086544 218689475 837154786 114926116 195675471 426300716 28629741 15566984 450847020 485248007 145295681 870093353 584844326 92995102 379594288 752404785 202868636 150079636 670111725 824550817 241630869 728140181 369137319 595544896 322116048 367720348 297830641 556798245 719435958 250227693 836380780 849925603 474…
Output: 7615657669

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Wild beacons of Nora - MEDIUM Coding Problem | CodeTikki