CT58410

Ranger's Golden Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the frontier camp of Duskwood with crates of segments, and Ranger the cartographer must account for every last one. 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 <= 1721; 0 <= a[i] <= 1000.

Example 1:

Input: 1555 747 696 965 436 522 167 456 380 960 45 706 390 733 688 17 425 477 882 256 739 397 119 987 131 148 413 194 547 696 984 385 694 246 868 511 349 652 579 47 906 328 531 370 976 674 537 370 39 122 17 910 143 565 117 957 69 186 465 357 122 720 315 729 800 423 192 723 751 918 67 399 344 282 648 154 259 50 776 720 77 260 688 766 470 142 454 949 599 647 660 374 611 781 823 488 782 437 286 14 823 886 721 74 769 368 989 831 799 472 505 798 834 591 774 279 4 503 621 748 854 77 401 148 261 324 684 492 613 849 363 636 352 873 338 297 456 703 301 484 744 119 861 541 321 957 79 462 660 187 464 841 75 442 813 681 886 257 449 515 928 591 872 51 838 333 208 207 740 980 942 589 63 645 969 49 868 30 61 280 652 592 189 557 126 524 834 612 224 364 224 310 775 136 182 333 835 605 765 854 265 374 499 56 196 3…
Output: 776468

Example 2:

Input: 994 458 716 641 446 772 225 750 754 748 255 298 737 958 377 219 642 376 979 426 763 312 630 28 327 485 646 951 82 44 50 987 841 912 329 194 214 277 351 230 563 589 366 678 670 194 572 329 777 944 783 52 752 305 967 313 34 216 291 29 226 699 673 425 587 279 170 573 662 411 206 887 434 666 427 456 638 105 881 285 968 580 467 7 742 382 207 532 970 530 754 51 466 620 873 776 242 165 66 219 24 159 873 574 481 866 484 224 114 183 842 757 829 990 116 567 339 334 396 481 963 363 879 878 322 133 10 44 189 155 639 43 864 267 796 775 220 283 356 565 808 958 223 714 527 150 761 667 507 317 815 117 464 936 307 96 655 41 454 38 82 46 366 181 366 297 308 344 795 498 915 291 376 724 10 939 602 986 917 809 946 860 149 506 905 196 81 483 648 965 636 428 697 319 518 258 756 310 851 944 473 566 925 373 711 89…
Output: 483998

Example 3:

Input: 17 367 777 330 83 859 688 986 956 360 474 488 244 678 536 792 337 414
Output: 3361

Constraints:

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

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