CT60453

The Rye Hollow Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the gristmill of Rye Hollow, Draper the accountant keeps careful count of the ledgers. Compute the guild dues owed, every figure matters. 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: 967 574573796 412778300 766065447 452610039 754019889 841898772 992595718 800953297 392342418 115374737 238949311 389089956 997991894 459367164 257149537 462021446 867955875 830361876 823659953 288258528 647259414 740783056 971111403 522179251 688823581 262226122 307179678 416647426 483040136 788544389 866324055 95292931 781853295 681448127 787238280 775158484 122946550 276768499 389281677 568570834 514789349 579087771 712653508 661803020 635934168 308196398 349077532 724740461 84977998 299851797 742016023 632789600 922565745 864087815 666528887 434794074 245000912 808629562 613511161 747967819 417083929 63457955 619375538 593744043 22791759 54515578 887602500 899148974 218210849 767633310 635583149 805862437 435984672 365471392 338858116 800601229 303466782 842740416 945515297 537390013 7…
Output: 9862162066

Example 2:

Input: 1832 452043095 986058079 615533676 495085260 592462308 599908185 340706274 854747979 875583413 503046814 868524330 774213135 744272304 262932223 952369650 669791793 544874205 740569012 747400406 62575757 312134119 662696632 96604533 959083395 711714862 664072413 174823955 920871621 217523557 838837061 440732449 709811034 346109747 307894386 881105878 655378610 46663369 414305770 200120786 496937972 404056590 971605143 852368624 570914315 747482723 468704265 162927248 326693578 714113851 873437331 137248430 315280183 726759949 557844198 884553250 581103288 179870901 650211655 511797187 351049498 268370504 817686228 155780049 766111564 947309987 894785702 775767659 384901309 104953864 769607826 64214922 271967365 542535878 702969642 788620340 174533913 276521299 444769883 636464796 937703149…
Output: 8744170695

Example 3:

Input: 977 445139486 859296281 652388182 826228421 605189233 853611218 321433566 287265460 244130158 826243112 116126310 406027124 904292158 347004007 559618563 724727478 166174937 183751329 19848028 832231376 19828377 697947936 145140880 985996441 717347643 758508908 700709949 821040435 420285684 877102304 723378295 159476102 216743613 249059704 466412988 673559640 642160901 253935508 138558972 838951181 454439473 855838418 549946660 407179772 509861374 141589294 687022435 837396032 637132138 128668286 84857640 387307052 936860889 870373952 413613991 464875038 244089370 43746752 310027252 89708888 130588788 818311376 910832943 557515076 84846387 838384238 734573268 8873752 355217956 242196154 290889925 891093329 833128687 414919309 722839730 310669115 966722776 115255427 91621242 243068141 90154…
Output: 6013971300

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rye Hollow Grand Facade - MEDIUM Coding Problem | CodeTikki