CT58641

The Gilded Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the pine barrens of Needlepoint, Ysolde records each panels in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2156; 0 <= a[i] <= 1000.

Example 1:

Input: 1726 339 993 962 717 473 581 71 11 816 735 937 574 466 867 91 997 61 987 984 152 148 37 569 20 47 822 966 571 440 341 767 740 146 804 674 879 41 629 967 237 713 607 450 362 357 276 666 66 284 261 329 920 396 232 467 364 901 55 1 798 757 993 84 855 290 276 824 657 196 818 739 723 687 203 880 103 938 982 801 178 565 622 500 377 826 658 760 699 416 312 492 185 541 466 812 490 96 44 329 180 321 582 682 278 928 58 560 401 120 851 359 144 215 347 744 262 442 161 963 910 467 741 947 563 99 486 148 922 678 760 510 252 794 266 450 457 398 213 252 95 595 652 706 508 457 591 753 253 20 919 734 705 220 378 524 585 304 299 310 494 678 539 3 739 50 754 682 177 505 441 61 748 73 328 249 87 916 461 335 499 102 157 772 116 345 515 323 759 261 260 519 132 425 952 417 383 759 930 899 973 144 494 560 958 653 …
Output: 863512

Example 2:

Input: 1023 518 195 381 567 593 827 660 730 373 882 116 363 60 721 436 812 632 119 26 645 957 99 8 897 935 581 709 63 649 58 655 929 416 224 839 113 359 349 178 169 160 618 444 16 283 894 756 607 425 476 452 472 895 263 750 483 953 975 93 593 211 54 140 646 576 276 488 953 166 984 481 975 953 631 942 424 956 706 362 21 996 364 367 279 703 972 944 125 475 416 507 282 598 760 899 145 926 614 246 604 574 688 319 765 78 961 969 923 352 858 686 595 293 795 555 957 878 969 707 225 886 687 595 488 305 879 540 265 204 954 961 201 441 425 893 491 363 208 336 686 862 858 202 594 855 166 693 517 275 217 6 929 267 29 571 421 243 85 974 694 343 144 851 855 313 307 257 88 26 658 238 414 84 296 298 570 942 362 534 558 426 769 191 195 233 631 280 924 714 822 665 489 89 327 915 96 468 726 762 956 142 546 947 735 …
Output: 504621

Example 3:

Input: 1052 785 930 304 317 417 632 419 598 240 170 986 515 616 215 38 289 249 774 194 830 495 571 974 938 625 162 469 393 361 171 889 895 333 694 533 987 477 815 707 475 276 274 723 543 142 471 936 89 377 89 123 32 161 895 493 589 327 618 677 733 134 943 587 997 673 310 376 270 439 365 957 189 214 765 449 204 918 352 181 254 6 644 264 708 214 284 723 167 813 614 569 897 906 312 456 970 78 388 707 977 112 285 246 258 431 298 30 534 75 973 428 605 809 57 41 689 557 536 745 423 285 267 165 355 607 610 20 89 680 380 976 787 108 878 969 78 238 646 29 992 382 352 525 427 136 60 628 141 644 856 773 211 873 327 240 54 378 105 623 602 414 148 346 909 497 461 994 254 659 836 696 914 46 14 105 64 443 753 2 60 587 370 527 615 663 479 700 305 985 258 682 587 114 442 631 174 585 462 331 661 635 496 326 794 19…
Output: 522594

Constraints:

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

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