CT47358

Neel's panels Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Neel runs the print shop at the snowberry thicket of Winterholt. Today the books show a list of panels, 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 <= 3168; 0 <= a[i] <= 1000.

Example 1:

Input: 1138 444 100 514 273 262 949 583 763 426 880 563 161 497 153 808 307 666 302 167 600 530 393 610 201 7 186 84 993 77 345 159 219 235 90 320 402 456 531 846 655 642 49 842 864 304 633 963 824 961 978 95 739 975 963 286 276 865 7 926 943 220 581 555 756 323 140 350 317 524 195 16 556 271 191 886 478 728 1 393 593 160 728 66 333 719 975 884 827 330 390 789 516 876 856 426 544 210 401 694 26 735 611 159 739 372 333 32 883 289 549 565 38 54 894 182 26 507 261 27 467 291 319 664 49 658 401 720 105 782 539 895 138 624 576 219 791 285 966 993 10 697 48 568 929 237 358 78 967 711 690 128 351 843 315 917 104 801 697 107 833 605 880 189 695 190 112 748 328 606 171 767 406 420 707 84 539 298 47 288 110 455 137 177 455 445 731 143 15 975 243 685 229 169 940 679 474 447 889 149 839 127 348 107 488 783 3…
Output: 559409

Example 2:

Input: 1569 594 375 787 111 115 515 57 506 300 854 617 942 592 546 77 300 927 188 820 667 622 854 521 441 939 23 984 699 647 266 96 796 555 128 257 73 569 744 174 586 444 503 788 264 809 669 560 749 381 187 213 893 403 0 950 752 346 335 675 108 556 945 273 163 199 232 335 960 734 122 763 208 299 393 365 4 468 20 818 638 309 101 693 132 320 482 180 345 639 184 205 615 854 628 165 268 309 945 685 74 306 419 926 70 474 396 220 483 849 82 897 370 649 486 408 450 190 686 692 443 447 759 528 801 206 835 626 63 815 674 524 410 567 427 259 456 947 125 856 126 956 346 129 460 519 593 527 568 916 368 108 709 66 347 752 488 204 102 192 208 659 611 516 847 340 999 351 691 861 425 621 840 332 683 876 541 82 581 225 526 175 765 279 819 235 574 651 772 503 236 486 180 146 796 42 689 654 756 995 180 146 999 478 …
Output: 770937

Example 3:

Input: 783 661 530 743 809 289 703 935 873 631 148 772 339 113 196 423 806 578 357 499 186 704 872 773 194 865 823 876 741 789 471 138 40 102 724 932 385 369 892 429 904 196 86 272 254 30 47 590 545 23 716 467 656 454 958 568 531 908 808 778 904 755 155 34 609 556 307 456 486 337 788 956 379 900 297 313 804 751 540 789 262 43 335 233 537 447 617 622 63 653 481 268 172 510 599 411 254 731 913 596 174 89 498 500 86 367 999 825 643 79 345 510 112 636 102 71 324 555 647 568 983 886 880 31 61 735 664 874 683 668 201 538 218 506 664 369 747 704 553 454 971 676 279 36 935 385 72 709 531 629 47 42 194 949 894 907 455 419 297 257 832 589 327 869 556 835 833 481 193 360 360 394 691 884 700 636 730 803 21 612 160 404 133 453 827 438 834 307 369 559 359 25 808 694 633 546 388 691 344 69 963 1 912 406 636 26 …
Output: 381920

Constraints:

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

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