CT42917

Librarian's windows Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Librarian found an old ledger of windows in the boathouse attic at the clockwork quarter of Gearford. The margin notes pose a precise question. 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 <= 1626; 0 <= a[i] <= 1000000.

Example 1:

Input: 980 825299 699079 518712 127850 191948 356223 653569 866646 76162 115778 241190 904024 853701 623549 92471 582240 150429 568948 369735 417175 942261 786576 452827 487997 683786 330486 154396 749925 519760 321144 655171 277870 699648 294457 248403 297306 963854 414634 276883 75522 209398 239731 141631 176970 42247 335699 587783 383438 163492 83634 328035 935508 911478 433827 794702 572054 380100 855013 302695 742635 441808 289480 113215 321820 613152 782718 228603 883179 615985 239600 853956 769535 477487 855565 157781 513546 792079 781034 267287 849542 813491 588063 698239 362399 488337 104990 626321 532672 96327 875648 829755 711849 841309 329949 231152 17923 579223 138872 490610 550487 39883 479075 398527 901331 306029 510251 648550 897300 665164 622626 869523 73573 452977 863597 106603 …
Output: 467386787

Example 2:

Input: 1220 803013 94321 75585 506209 187957 534524 399967 714665 400917 385255 568868 628521 903191 332084 867887 101130 4629 49789 287436 790618 953873 126634 979851 470717 165795 201647 253783 257080 460781 739919 691651 946600 740504 616087 799584 636711 967707 399533 70578 404579 289128 219034 184884 360426 44440 960812 443915 131783 278822 196365 753456 15873 181739 769135 395726 393494 770966 620003 670624 649000 709314 85480 492358 615541 708076 248518 770221 812591 860180 848205 682886 145001 419204 657115 261934 733472 673214 163493 922705 163811 651982 771531 914710 299976 63458 156313 927060 817047 878606 592065 725512 817379 840145 757615 565582 331341 22553 323721 286012 258819 957886 546199 699672 274006 97914 599626 234826 938813 779533 716889 508158 528873 681911 854737 280331 30…
Output: 596456774

Example 3:

Input: 1573 238746 785049 304811 37006 551733 828069 202829 197299 263639 386870 931352 391019 240131 630468 896221 889576 971289 542220 365138 672904 847637 420616 720211 704183 370874 190792 700519 414900 839248 351720 118307 444152 193814 636394 499504 87238 45100 962625 527542 508212 193283 812712 286863 80603 955198 561807 632795 621094 372063 782611 45413 621750 109593 743858 327332 557253 878520 541542 98542 96766 910606 4210 459069 524069 104832 651789 180150 972570 898768 35330 86855 120108 361356 628886 345246 219284 591776 564765 976909 811139 651039 146478 569780 648082 23744 796666 770873 294053 806076 922188 226271 945657 916529 859504 506901 378853 626060 250435 381150 53630 745830 483028 931353 551271 800075 459927 225402 860320 930143 464260 110445 324080 516039 182966 1536 62594…
Output: 769149179

Constraints:

1 <= n <= 1626; 0 <= a[i] <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Librarian's windows Rain Ledgers - MEDIUM Coding Problem | CodeTikki