CT60094

Bram's Wistful segments

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Bram the archivist watches over the fen lights of Will-o-Wisp's stores of segments. A careful computation stands between order and chaos. 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 <= 2052; 0 <= a[i] <= 1000.

Example 1:

Input: 357 794 570 636 456 83 637 781 307 821 940 448 103 592 329 867 38 908 958 451 843 136 473 626 452 344 791 118 193 988 678 228 456 532 54 556 697 228 777 98 764 381 997 752 674 758 422 20 145 491 512 194 575 398 661 746 132 984 806 676 340 522 61 789 548 138 956 373 689 987 704 4 881 368 542 267 193 847 219 550 534 219 250 646 439 665 419 241 984 912 796 706 950 22 179 667 688 587 353 217 402 886 85 607 530 671 993 13 320 535 871 219 244 581 78 323 612 193 91 424 398 957 22 267 870 681 376 518 771 800 223 972 853 192 482 931 255 862 141 790 897 453 814 5 622 604 39 481 495 459 542 419 464 39 123 281 937 773 287 289 347 29 30 759 360 823 83 188 301 3 445 301 492 315 892 804 790 31 945 701 806 278 595 395 309 610 800 693 718 880 393 334 939 555 450 61 752 138 868 185 95 273 385 995 982 85 279…
Output: 163387

Example 2:

Input: 128 127 637 67 59 339 122 69 307 13 110 836 625 376 247 521 555 192 446 991 749 487 252 101 99 687 664 602 3 737 312 906 251 525 142 751 22 84 643 250 171 685 797 655 277 401 775 468 993 219 636 154 693 736 62 694 727 327 428 152 397 92 511 600 652 264 906 327 680 549 656 278 180 217 409 872 513 977 334 988 274 196 739 34 598 851 205 724 364 864 968 846 252 18 651 243 29 267 930 578 908 842 758 667 600 64 990 311 402 190 559 889 647 936 57 583 274 584 326 487 929 977 487 47 160 51 588 978 640
Output: 59958

Example 3:

Input: 480 940 82 262 823 574 357 599 742 911 561 451 649 595 744 686 834 104 922 594 244 640 963 177 547 970 312 231 822 22 517 506 572 550 229 960 868 224 491 351 55 921 293 71 570 100 438 857 796 85 807 205 921 462 309 109 892 797 478 525 83 47 574 871 477 581 830 350 615 799 822 371 824 528 759 899 462 950 913 600 290 30 374 95 328 523 20 427 602 883 475 938 558 711 275 62 781 996 786 762 790 605 326 366 342 704 617 762 247 39 782 907 243 918 526 658 883 944 828 817 33 576 89 359 670 682 759 268 17 795 663 866 275 253 843 606 78 915 482 477 521 185 853 672 474 227 698 56 424 676 520 117 917 722 348 771 128 957 776 684 693 971 332 330 409 593 560 686 757 602 62 649 891 547 946 303 903 840 85 428 674 454 213 684 274 947 185 540 94 160 743 999 20 390 970 614 201 522 136 558 135 844 493 47 53 279…
Output: 230416

Constraints:

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

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