CT42307

The Rain Ledgers of Frostgate

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Darian the clerk watches over the northern keep of Frostgate's stores of scrolls. 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 <= 1294; 0 <= a[i] <= 1000.

Example 1:

Input: 961 696 926 896 939 520 329 28 979 427 745 376 208 377 685 941 625 412 53 273 816 254 801 556 204 228 300 493 398 834 354 626 785 887 801 109 330 383 629 60 761 914 277 105 934 604 270 635 108 343 978 691 188 542 862 671 24 171 501 37 621 62 765 265 277 726 129 138 769 525 882 451 254 966 10 334 635 483 658 352 670 648 337 798 277 576 384 741 339 163 471 906 631 248 32 199 238 10 529 639 15 157 788 30 350 883 875 845 670 656 366 235 456 148 832 305 268 211 915 333 613 934 258 133 788 741 461 10 707 247 616 849 94 427 117 683 204 986 879 102 584 875 382 595 987 726 365 822 282 3 828 568 783 998 412 866 240 284 906 504 293 702 287 943 389 507 727 803 746 273 936 584 722 540 160 427 597 560 814 267 532 236 435 621 477 827 442 83 909 943 304 306 451 803 636 846 924 473 141 602 36 617 151 952 7…
Output: 474393

Example 2:

Input: 1024 391 530 655 27 289 250 791 320 716 163 612 52 216 341 215 464 436 980 873 536 470 292 639 76 114 968 434 520 160 677 868 608 432 775 233 412 408 237 509 560 209 615 740 868 517 151 688 202 189 467 184 642 817 776 95 449 120 827 729 441 437 754 218 605 713 177 122 721 161 850 876 361 578 288 303 483 658 199 354 250 663 226 540 292 405 346 342 159 325 665 18 241 208 988 185 649 264 239 462 858 462 753 427 924 126 385 205 347 357 620 990 369 39 215 246 413 649 216 405 152 672 307 824 574 665 1000 39 572 512 722 215 557 693 100 915 841 21 364 35 596 882 524 425 518 774 925 358 956 273 619 818 712 94 882 685 786 476 49 120 866 859 654 25 810 952 331 70 287 247 543 373 85 566 867 886 765 890 567 220 426 806 384 209 712 162 466 182 850 858 711 711 119 867 347 843 440 615 833 482 552 410 503 …
Output: 490122

Example 3:

Input: 729 840 52 536 669 166 195 718 229 684 330 374 96 733 314 464 94 689 624 757 595 634 401 879 386 882 709 113 214 469 104 43 554 444 782 375 785 181 563 794 806 926 367 972 792 272 476 211 76 588 188 971 116 951 949 433 88 921 333 235 171 399 614 100 829 141 921 124 207 962 211 66 458 50 43 344 936 625 433 796 568 304 361 602 761 964 279 733 927 273 179 883 510 253 171 511 487 78 512 816 540 700 37 230 487 821 232 460 199 985 448 985 972 549 234 533 242 737 258 12 169 883 457 388 614 616 361 50 304 885 392 698 829 548 517 800 502 498 588 387 941 681 252 714 988 328 156 492 525 998 838 968 463 695 131 765 113 799 761 645 628 288 482 781 251 954 837 210 108 640 181 906 64 455 405 882 805 467 931 869 143 873 991 416 100 482 292 662 787 442 467 1000 233 290 765 410 335 680 826 281 96 476 521 28…
Output: 351785

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rain Ledgers of Frostgate - MEDIUM Coding Problem | CodeTikki