CT51849

The Tangledeep Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the kelp forests of Tangledeep close for winter, Hestia must finish the segments ledger - one figure at a time. 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 <= 2361; 0 <= a[i] <= 1000.

Example 1:

Input: 1032 20 511 89 147 951 675 445 815 583 777 34 166 88 662 307 552 892 485 639 23 117 144 520 719 823 618 520 93 353 128 292 82 941 967 3 995 233 383 598 452 750 667 221 359 20 508 741 358 386 800 700 81 352 736 229 585 864 976 716 534 228 977 55 769 130 507 931 325 848 178 423 476 596 370 745 502 420 562 278 62 859 400 964 369 218 278 775 652 528 768 427 414 209 809 955 277 806 107 657 172 173 264 914 112 42 638 358 77 12 207 159 700 697 63 338 697 823 435 225 901 139 78 972 428 527 912 829 951 715 613 343 127 288 12 884 761 533 995 648 203 332 774 901 94 885 301 865 253 327 168 866 419 29 694 535 451 634 24 533 381 570 878 253 97 543 12 633 746 216 576 242 560 69 626 645 61 513 147 1000 321 359 387 4 503 159 112 611 908 326 803 104 94 857 526 157 832 633 919 370 413 152 34 410 90 913 464 2…
Output: 520223

Example 2:

Input: 1275 619 795 540 475 346 642 661 11 151 361 994 497 339 929 653 723 840 570 165 309 584 883 777 772 943 652 317 590 70 548 46 3 290 381 985 323 185 175 732 884 173 420 571 791 520 460 530 984 272 838 318 744 208 124 606 640 780 187 8 542 333 16 27 388 941 194 225 779 952 544 168 228 441 827 540 173 175 952 522 654 865 798 774 262 340 609 604 23 404 971 741 22 202 537 569 915 708 731 731 907 584 175 144 938 867 769 113 227 855 914 581 901 747 453 576 638 194 539 512 175 977 93 695 418 793 261 437 342 775 802 802 42 329 128 156 731 731 571 495 267 268 218 617 823 125 522 91 401 496 524 543 575 150 415 227 780 990 206 176 92 321 279 999 284 760 255 208 832 394 934 734 829 850 29 70 296 493 833 888 798 165 989 89 949 380 928 521 778 793 433 794 602 393 711 264 558 180 713 550 965 557 306 730 4…
Output: 613937

Example 3:

Input: 2320 373 172 216 629 497 265 323 798 689 93 81 456 238 165 481 912 217 746 858 31 475 567 651 86 519 196 875 27 148 511 925 841 964 904 286 293 271 599 900 937 900 175 108 817 42 276 808 190 719 787 799 697 404 529 545 802 751 331 635 324 669 869 155 658 277 174 953 421 4 219 438 798 514 380 430 227 768 59 712 538 453 70 81 432 985 483 541 703 29 823 921 364 362 432 705 383 266 727 957 539 633 136 11 564 913 861 706 752 191 461 887 903 523 436 694 405 508 877 587 660 848 202 348 101 919 490 661 434 762 624 937 933 116 544 110 119 308 581 883 196 917 449 133 658 240 155 975 990 925 349 600 613 947 627 700 568 800 368 961 640 602 585 383 80 224 373 214 644 513 239 829 142 559 600 24 234 403 689 72 73 541 796 780 214 663 731 805 890 65 30 992 786 145 798 328 888 274 779 753 853 952 888 353 62…
Output: 1132546

Constraints:

1 <= n <= 2361; 0 <= a[i] <= 1000.

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