CT41474

The windows at Sleekwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the otter slides of Sleekwater with crates of windows, and Ranger the cartographer must account for every last one. 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 <= 3570; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1197 802730233 443604683 404711990 249163637 11645285 428123470 423054773 275863123 706117105 870506278 176418635 76536890 915649059 733141980 286700881 141925157 193090983 229029067 3055753 218326412 674000672 651098113 304457448 777846872 817624664 919334936 973394859 578515271 289494481 194757843 709282967 466428166 14271632 772555005 712099521 143939478 110205758 616276775 139665456 42000074 614648071 950745194 911232575 976407550 528262844 414867995 282321599 979279142 729173179 273720072 187284051 858760788 302570674 151637480 960096174 642727604 258993723 132051515 452560439 865894714 53917588 391873919 524225521 978459276 28923545 727362455 841332624 575582128 110920075 790886740 594196254 9914195 91506941 656998776 289025647 391283385 494689704 934168457 698561379 611493096 253382…
Output: 591854939579

Example 2:

Input: 299 631827651 281565553 232056427 340898601 399247114 698663455 698268412 308712623 571865583 134564970 25154833 170737173 357737740 596407939 163885884 409888267 444127964 616133026 647478170 595634927 399104422 201087756 616379750 896171526 814789894 349084689 243251238 12839338 774079447 493537983 814074206 319002599 189475669 617189319 329712694 979599519 332321891 889220495 296086189 817021112 589595779 164972720 814934796 205104513 633782052 581276120 946171280 952822401 499327071 504935342 143346067 397132074 124448085 451772926 527532678 618191426 884048169 189450471 863037366 16322547 611837824 31348665 46398975 772022443 93799898 334343292 390027363 772350350 909609663 196532819 712453435 599796329 197974470 85670704 782698016 630521332 424251039 661777625 45257261 264778365 5859…
Output: 140435534462

Example 3:

Input: 3308 710555249 804135505 254088967 764851963 209959871 751125020 157350028 713619266 283767800 277876354 888910762 93904671 787515401 989716975 661554607 777781647 919712425 677060133 672032173 248880337 832550269 413608609 214561894 700559627 185494570 863149474 803623120 79972226 707578637 41171121 717191392 481165114 783240849 575633485 845071112 576844139 703465797 257454580 982678686 875450327 355020877 420921378 525670811 841318995 763700604 407567627 624403011 447618117 436567137 390067152 805970435 473607000 266922124 144312881 311701307 481318831 897045765 680350728 735882776 867021910 918541411 17498636 782287149 493739708 670066060 894078251 812703216 924798527 307863847 853278024 530658364 861337729 26420987 840208870 950672589 576079236 574743597 316640488 421612546 92648639 8…
Output: 1639653334483

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.