CT59370

The Slitherwick Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Yash the assayer watches over the eel marshes of Slitherwick's stores of panels. A careful computation stands between order and chaos. 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 <= 2903; 0 <= a[i] <= 1000000000.

Example 1:

Input: 621 653352624 773958883 635920278 772839414 330104132 630805589 674290468 797075363 29765614 233606793 789644217 594005566 415626493 62146973 733869027 693525383 135588294 108258797 822472678 473150578 699060740 427083384 927924052 218781815 28506440 114933765 832632864 953863679 95651291 719930972 917597105 939826568 249371083 113998143 560324929 97869847 968328570 448604521 744515809 493481891 891239446 438591980 609114669 74432211 970301930 145571177 504774746 3813417 211791090 773267697 70331566 328533681 698436060 788535114 2559775 780222417 899462924 602769311 339491359 466857504 649527853 638137316 133856171 586300741 89914453 802034654 591513281 280999352 237469682 502349466 906458061 673777298 458252449 132235236 79615356 84012785 132757101 969892739 418281062 548117643 720528293 …
Output: 291870623572

Example 2:

Input: 38 942718997 937223631 169525488 7081848 883654168 110653605 125260833 9311767 565916971 461559997 146567199 87421576 633956949 322497976 89297481 274845049 239174029 746844338 456222792 579665370 221579241 229015234 897800579 172639928 108403205 659477944 865158299 902084081 330080145 29945984 688814819 478644220 466579589 235309977 813718121 771998656 15907907 440674554
Output: 16566270798

Example 3:

Input: 346 342347756 850371275 127059983 507187493 387111149 359849339 544840413 961326648 133569340 124669733 993507625 364189354 279979583 442546542 676365006 957633784 821010754 486440355 790884628 291645423 946618296 572907043 137265217 904047008 713700611 85116578 612827222 140431375 925425295 307050659 243290555 439238200 821756170 460090527 239569470 742229806 564620885 730574517 479720873 411898653 394483853 211344207 954874443 812088325 491212488 74318033 173328907 305949382 721613099 555506004 271480618 833626497 741691256 953153484 588442259 82458779 608483741 132197617 482822608 3692891 408047605 5459324 28290995 216842985 792661773 974787516 719307902 128576293 639081137 608456882 897522009 993539843 315131364 458857152 748538052 529666354 878905716 262408773 435006646 851687243 2812…
Output: 159949654303

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Slitherwick Rain Ledgers - MEDIUM Coding Problem | CodeTikki