CT61340

The Ruby panels of Urmila

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Urmila runs the greenhouse at the lantern lake of Firefly Mere. 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 <= 1263; 0 <= a[i] <= 1000.

Example 1:

Input: 774 627 197 457 937 314 557 232 459 514 978 709 770 705 976 977 375 418 291 347 889 91 328 821 423 264 776 877 0 930 2 648 626 803 632 492 619 213 961 30 264 678 811 85 622 550 583 815 451 659 371 920 454 936 147 443 306 512 635 633 652 426 724 327 35 645 564 524 143 947 236 194 426 515 811 785 669 278 700 618 626 559 963 604 484 76 390 830 435 795 370 293 404 583 52 554 336 220 3 977 342 613 272 594 49 570 322 85 867 715 818 664 542 450 650 728 5 273 567 820 985 279 606 628 879 10 548 649 741 479 793 749 632 120 780 961 256 613 965 6 97 784 990 494 392 639 943 649 61 831 817 154 101 407 312 482 424 578 268 860 101 182 879 997 284 863 747 676 339 4 752 615 869 243 556 786 430 186 354 620 173 245 622 505 135 431 553 301 180 355 427 974 341 949 252 587 534 682 881 981 351 837 181 138 40 961 …
Output: 369942

Example 2:

Input: 1200 838 841 199 849 656 409 968 148 341 932 871 910 966 202 817 641 874 894 447 378 502 615 902 826 46 670 585 830 510 702 162 342 208 923 43 703 382 968 185 872 463 496 933 683 831 75 794 566 665 671 931 595 47 721 74 299 704 134 496 330 347 332 809 865 219 384 679 752 781 507 254 50 558 521 917 932 749 722 665 943 455 768 56 509 558 86 763 10 544 619 998 877 941 254 269 689 983 266 65 849 428 968 356 130 922 508 144 452 36 687 339 324 393 727 652 781 274 544 329 68 630 554 349 91 228 332 373 692 550 263 171 285 399 157 320 888 59 705 744 467 79 404 79 773 258 359 307 209 325 362 466 62 963 787 546 606 180 815 558 818 469 384 416 944 117 44 571 744 444 384 154 307 978 398 578 191 206 929 241 644 543 664 804 779 530 700 29 176 962 308 246 184 364 200 308 514 385 924 157 910 914 645 660 58…
Output: 605915

Example 3:

Input: 524 928 627 384 879 52 137 848 51 635 982 919 437 799 767 829 612 290 720 851 971 688 320 870 294 320 280 287 356 467 815 566 761 503 519 665 677 430 505 271 864 737 231 799 819 845 112 87 694 611 819 811 271 937 775 580 396 494 694 948 154 119 204 667 36 518 947 797 379 720 219 469 347 883 544 269 332 833 19 870 742 356 652 753 140 35 655 661 941 400 378 389 951 350 667 624 838 673 260 567 529 206 941 201 452 714 954 282 346 593 180 881 442 731 716 981 70 410 862 473 262 683 328 436 252 402 632 725 80 822 303 145 841 345 103 926 127 702 74 282 677 856 201 173 516 770 909 920 971 296 494 121 564 119 856 515 77 925 5 74 290 674 606 225 429 938 127 536 130 842 632 886 347 285 350 120 215 10 434 930 300 136 461 316 455 156 741 680 826 794 325 484 763 879 830 536 751 662 19 237 31 639 308 120 …
Output: 245751

Constraints:

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

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