CT43289

The Verdant segments of Wren

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the river town of Willowford as Wren unrolls the day's manifest of segments. The tally will decide the next shipment. 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 <= 1573; 0 <= a[i] <= 1000.

Example 1:

Input: 804 664 215 695 875 486 700 162 958 524 787 125 834 232 941 263 979 91 126 815 336 22 322 692 646 738 693 387 407 642 380 65 889 472 709 636 816 580 833 117 416 186 241 299 156 595 538 892 465 870 109 913 27 422 535 281 353 125 876 6 425 894 185 403 25 550 630 257 657 898 780 343 583 602 392 850 0 888 285 677 214 152 423 592 332 286 353 719 965 339 517 649 866 934 853 56 471 717 710 786 858 417 571 502 492 816 411 333 170 76 747 170 244 837 42 41 616 567 867 102 519 210 954 289 35 598 834 267 973 238 565 566 483 144 26 701 540 466 496 111 364 657 672 276 386 944 578 243 587 53 993 813 952 965 859 360 904 356 538 409 410 371 390 410 887 631 932 808 519 778 909 792 977 139 849 934 457 664 437 68 134 848 886 45 231 321 967 557 456 2 432 574 636 976 688 293 337 830 676 623 75 16 523 232 461 59…
Output: 388986

Example 2:

Input: 208 242 964 522 872 977 264 294 804 272 521 260 101 465 466 521 494 676 360 242 66 489 274 24 873 227 293 221 981 914 327 489 884 966 163 481 32 941 300 569 338 550 119 668 689 727 849 213 407 374 239 436 918 849 572 967 53 233 694 273 590 521 414 344 956 97 663 996 556 17 594 59 572 70 935 295 265 305 48 70 401 839 721 378 907 658 547 538 687 549 591 980 481 355 807 630 832 371 278 841 682 215 784 47 898 750 247 466 723 480 625 333 541 485 697 598 940 554 866 769 102 87 146 491 716 444 644 955 478 83 393 553 361 169 837 388 129 883 259 219 576 526 311 496 362 836 228 610 153 934 833 427 33 988 681 296 521 655 910 938 444 954 631 129 803 870 13 549 189 268 434 39 535 601 228 341 587 174 203 203 527 98 269 168 667 831 617 595 136 913 932 885 713 74 140 71 3 894 266 219 815 807 712 81 319 41…
Output: 97443

Example 3:

Input: 503 246 329 839 917 874 254 883 489 66 753 109 366 733 254 744 364 893 738 813 951 974 473 41 978 633 608 506 683 333 440 24 264 450 954 184 309 467 900 104 266 934 541 378 848 191 21 934 298 522 10 193 794 397 502 16 690 147 29 966 152 811 405 927 704 613 388 3 232 260 440 377 744 268 443 204 842 777 988 344 249 248 318 730 894 609 245 862 481 642 54 658 597 523 148 256 769 413 305 14 418 66 619 162 612 783 10 554 699 515 174 482 910 752 425 797 744 610 807 460 173 937 51 10 36 235 328 962 703 620 229 406 944 957 792 168 256 261 992 986 478 765 456 699 429 441 634 61 644 800 753 913 846 234 275 538 692 922 136 100 77 863 894 967 125 938 990 782 688 781 334 3 45 262 373 388 739 598 797 647 834 835 980 691 880 829 243 378 124 778 446 767 86 571 311 701 310 938 650 332 731 364 537 996 573 67…
Output: 238567

Constraints:

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

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