CT55487

Elio's scrolls Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Elio runs the counting house at the fjord village of Deepwater. 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 <= 2983; 0 <= a[i] <= 1000.

Example 1:

Input: 664 873 557 224 299 570 635 511 590 186 842 122 225 627 697 7 128 20 816 486 455 677 736 377 640 935 294 596 50 285 712 398 388 573 543 770 103 577 387 129 499 726 566 114 745 368 4 346 436 585 476 312 371 334 936 230 37 13 653 717 64 3 156 200 574 624 772 852 336 202 651 536 390 902 534 145 999 132 111 505 664 664 809 460 174 516 655 6 61 442 646 192 868 645 234 384 842 919 358 64 589 539 18 368 863 610 702 114 118 563 528 485 999 835 764 983 482 263 117 206 521 870 288 379 649 472 285 324 265 662 452 470 672 554 402 620 666 208 998 9 656 480 678 780 629 619 416 69 628 354 61 374 431 976 171 610 250 607 53 424 78 52 583 139 183 560 739 387 619 25 599 975 792 222 187 315 345 885 242 695 899 135 493 679 578 689 411 502 281 467 185 627 210 936 710 856 319 399 293 703 850 913 238 397 738 835 …
Output: 323515

Example 2:

Input: 2888 827 111 554 47 996 173 954 155 57 133 134 40 787 500 552 211 947 798 314 158 95 213 957 78 840 76 540 579 436 250 380 183 952 81 321 134 465 948 963 249 335 926 535 762 815 97 843 174 521 990 389 393 904 94 131 106 892 697 196 752 642 497 1 978 591 896 194 751 400 778 863 379 365 824 74 630 422 218 381 659 80 918 309 908 442 776 11 858 150 640 938 344 867 135 844 254 234 444 305 277 925 359 493 561 301 334 410 432 448 562 52 580 890 15 592 599 669 754 535 392 968 817 787 614 993 610 721 607 875 612 119 692 360 841 87 6 959 785 965 329 982 50 491 252 544 724 959 874 16 174 289 523 194 165 409 474 368 961 213 448 426 318 603 543 915 867 311 2 794 18 683 578 976 710 530 605 856 802 389 755 744 822 752 697 349 425 901 569 184 279 198 716 858 675 41 331 527 634 713 89 406 153 653 246 367 2…
Output: 1454211

Example 3:

Input: 1276 648 105 835 185 319 918 440 752 528 33 429 664 849 2 261 595 144 222 383 177 567 225 151 701 831 949 855 1000 756 840 344 266 936 481 845 570 253 19 498 742 750 413 591 142 299 105 283 303 964 707 921 750 499 118 803 524 669 583 283 838 778 50 199 347 8 965 712 228 356 575 774 472 93 227 87 29 890 406 851 129 277 712 991 638 689 974 970 759 369 129 337 570 613 358 616 127 72 843 563 131 495 433 264 702 844 766 48 663 457 599 922 486 914 356 354 714 985 277 154 901 503 140 87 124 155 15 289 293 425 446 297 671 170 468 851 554 924 198 905 271 399 166 24 574 134 935 900 957 19 710 95 48 80 353 260 917 630 140 606 246 572 749 717 741 306 630 541 99 336 568 434 862 434 95 968 917 553 58 367 565 558 810 253 376 637 252 729 962 63 439 546 178 529 831 413 0 794 93 900 868 502 500 550 550 919 …
Output: 628975

Constraints:

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

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