CT40661

Dino's Rain Ledgers Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Dino runs the brewery at the steppe camp of Horselord Plains. Today the books show a list of scrolls, and the numbers must be worked out before sundown. 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 <= 1406; 0 <= a[i] <= 1000000000.

Example 1:

Input: 576 440788564 61411836 486964061 767906335 937440102 83367707 293683483 709610483 146001388 418010189 179601371 713623950 133597300 269501019 916841891 402336236 901883567 262189953 54117817 603586694 284344622 110908508 122323238 819811611 229125854 100977872 867394320 421567767 428545286 974609726 451908215 628307261 578827413 31329610 399959904 846785602 661132442 870401687 959181306 297228165 159380814 527541769 137083089 235420879 900903077 156009455 161985115 656263749 137933327 229738634 95851324 211117877 607194328 576072945 84738682 725614140 967115027 680545583 791492104 141071933 505076734 306682628 549335426 409074638 593052836 386300487 499252299 638455344 663429110 637193623 227621712 132401201 595029321 127495229 681349910 411573795 30046184 727023681 144361562 376260850 158…
Output: 286557737703

Example 2:

Input: 1295 992930226 118387494 909415931 619767108 798099892 135370643 340857960 465727079 506786243 84289573 396795681 687240509 403986862 51245643 279358805 270430305 721261686 604939505 659383483 397633312 782940644 271682630 857531500 408685191 664229605 385576389 295324286 918675181 747879132 775182085 404657060 342268829 784235777 46229189 804749423 420908787 283450446 872931405 30599640 731978677 160388589 296833977 8539973 693805326 825146669 36247353 729011987 469150694 791318173 167044450 221739587 475274811 879399576 960586495 930564912 110045619 122918206 576892934 140175460 119752277 666346026 345157259 602738938 791624919 335478614 762560890 787433519 789306201 491432370 810282297 736603016 290274843 6852339 842886065 258397914 484294740 798907541 670247905 146639658 639087913 6656…
Output: 630285668259

Example 3:

Input: 483 228049406 18459387 845933705 821241646 658404047 815930067 412531924 779689958 859924690 771388258 3530118 110654229 1303837 543570088 820208357 103077754 927392436 723194050 486823479 947191382 765628032 781774520 380174228 191736697 411434725 985208228 96401213 747913172 990461283 272819035 985804738 89706807 674225707 976918623 246366709 879693891 298871973 591827438 889768595 618727797 29230863 260898290 692517464 862840776 425222415 98120661 869304327 185234436 763017061 727091037 32157685 351000432 580621342 664235710 938743537 998546487 812490050 974369269 358170863 989239514 562106117 130068591 720184557 177179016 179006682 766478081 504473134 93283219 204920621 148792232 25620341 611993510 21821125 899703615 570960589 391512921 408299152 534923249 535659848 477899401 273751279…
Output: 222641379331

Constraints:

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

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