CT62479

Potter's Vermilion Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Potter found an old ledger of stretches in the apothecary attic at the copper works of Verdigris. The margin notes pose a precise question. Task: Heights a[i] form a skyline; after rain, water rests between higher bars. Print the total trapped water. Input format: First line: n. Second line: n nonnegative integers. Output format: Print the trapped water volume (fits 64-bit). Constraints: 1 <= n <= 2720; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2549 285761441 66815502 780458525 630002957 437158044 520265427 900171056 960509482 653932317 196509732 150827351 482238473 135243243 68905117 601100318 598938361 941273447 137611949 747090862 453671054 798856970 305959774 621583491 236146641 557456585 21750817 796672407 176254047 841100279 816088980 547660717 416892521 951333645 423853541 421464892 903084240 12091769 653857189 63222896 689910232 809875573 928088443 711933091 855158470 97223298 441858165 775617687 100193881 369086608 521904791 908936087 168173666 219703812 571340442 54060165 302083567 251929013 73045632 947322488 695140913 236666813 243771156 208131105 607618476 946146345 28827687 43313281 884762863 819170646 464656173 844959894 602378745 227311308 411999618 613757911 590325734 23974175 755439833 10155619 747383833 5139395…
Output: 1245764784844

Example 2:

Input: 67 609928602 77234001 45870617 953875417 517809403 967384386 718205445 951210247 528036048 582999399 64632150 110838020 555222948 878882528 462392902 423006605 796607354 515268676 559166241 142894868 383613247 421934978 214381293 574946215 405548479 784831804 748081928 138328780 692839719 872345558 351587956 335917192 8512022 758306093 393286619 319629462 56118773 497288319 633278418 350546949 160808361 12512466 619514504 761174289 118450112 756898988 938872352 480258519 52281784 638702749 389976544 648444477 154024325 391418706 120038121 874960567 438466609 326460566 355287344 285615654 991316660 496553592 977783523 750828566 486311820 103214775 245031921
Output: 29639768249

Example 3:

Input: 1322 709296730 643268507 998360995 353398831 929122719 66043099 920769610 123029368 376497233 713077166 168516588 921685186 871386063 817344861 940992420 2993883 318543034 437509420 495551405 955562806 24387870 716447040 693813918 325375907 93323434 204639165 611055738 2422200 957566874 743165565 758175301 25385613 796893259 949182829 453513189 526891562 605682016 788587301 483001011 151420248 373935323 905044742 939166742 941663465 939636499 730268736 358857359 822371999 584670471 658863872 845571936 747563027 227902739 344880733 343084207 950066585 480007724 261451137 361989453 711526789 68179710 830628263 599412797 158234403 994441390 849492705 408658666 825588627 939824545 982982290 637828029 138939613 285696250 709891458 928728905 885070442 848814851 715300129 667839704 795379749 3474…
Output: 640282345190

Constraints:

1 <= n <= 2720; 0 <= a[i] <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Potter's Vermilion Ledger - MEDIUM Coding Problem | CodeTikki