CT59610

Wheelwright's Ledger of stretches

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the garden city of Petalbrook, Wheelwright records each stretches in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2456; 0 <= a[i] <= 1000.

Example 1:

Input: 1385 120 373 647 431 186 587 68 790 645 1000 381 662 499 330 400 284 378 93 499 318 446 281 33 465 605 458 703 829 423 6 398 977 438 854 716 71 729 396 141 540 286 208 767 698 787 857 331 184 356 275 1 830 11 217 407 84 718 724 758 671 200 453 428 263 354 727 785 68 592 748 434 478 558 649 349 595 982 793 563 84 398 223 972 301 514 618 725 790 963 667 118 23 542 97 562 561 247 776 251 281 775 687 848 234 258 45 610 374 832 81 872 77 158 845 308 96 201 319 346 218 925 321 842 487 406 897 78 789 705 254 347 759 19 385 580 986 734 587 848 451 983 701 636 660 871 387 902 942 886 971 435 819 478 410 488 154 640 647 913 187 936 989 269 490 318 794 322 547 597 612 116 302 393 530 226 338 112 485 591 573 978 973 148 330 892 711 247 27 288 630 106 185 940 99 937 476 348 843 891 738 746 218 228 231 …
Output: 649961

Example 2:

Input: 1149 771 97 227 347 322 221 404 341 363 576 360 443 603 789 361 919 912 882 949 834 607 257 945 194 837 373 560 461 707 544 824 662 60 34 212 20 702 86 900 589 893 391 89 4 243 352 780 336 949 924 850 901 564 414 510 557 829 926 246 50 8 159 884 186 813 616 902 48 169 652 212 42 536 987 692 773 188 253 294 402 271 946 796 320 631 949 500 445 394 402 679 492 760 378 473 854 373 503 441 740 263 580 372 341 829 109 976 936 845 950 834 979 580 866 682 467 553 341 654 631 973 984 754 964 303 542 879 245 860 346 21 432 199 785 429 972 274 760 197 496 930 501 827 955 277 359 458 349 219 421 413 937 170 481 966 452 973 943 801 895 1 585 298 284 962 154 166 248 334 654 596 930 65 778 102 316 393 710 355 845 128 834 664 683 622 976 827 716 642 429 811 93 87 253 797 581 913 406 888 240 268 255 428 44…
Output: 547622

Example 3:

Input: 116 741 966 10 952 733 321 834 180 761 584 340 101 813 322 721 107 263 764 569 853 954 655 848 816 60 10 975 167 750 466 135 168 428 244 610 887 69 190 575 163 95 791 859 176 698 316 874 216 323 563 279 787 223 131 709 573 346 949 777 801 475 658 339 676 362 627 212 324 597 650 852 690 491 537 860 4 475 490 656 984 337 106 539 685 549 585 95 795 177 154 193 923 99 728 528 470 121 551 157 24 931 845 494 118 388 794 775 187 485 807 694 290 843 609 556 418
Output: 50202

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Wheelwright's Ledger of stretches - MEDIUM Coding Problem | CodeTikki