CT44343

The Marble scrolls of Ojas

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the river town of Willowford close for winter, Ojas must finish the scrolls ledger - one figure at a time. 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 <= 3246; 0 <= a[i] <= 1000000.

Example 1:

Input: 2438 128247 75628 985673 655275 585758 693313 469638 250254 216687 668998 572037 382067 817654 87736 177499 41665 108911 239225 452608 646798 140702 351504 310300 772866 692641 558643 845591 547704 374139 833817 590 881549 459829 800872 961952 710301 5317 93596 834896 32300 594774 629407 869596 302307 458576 898078 176688 334803 72570 702552 632834 304756 622423 434876 521699 892747 270656 299332 999553 700404 232444 410944 30379 807640 142895 158614 420785 718055 437627 493700 926509 683846 43840 700188 791602 88387 888475 598480 769962 980235 408901 326218 876755 349202 159344 596540 530302 127406 83316 480083 446521 906180 557154 771329 371574 767740 635282 586111 739059 301592 88479 819284 228409 73444 279823 609077 349925 843720 504564 485835 889794 903318 382407 46571 390117 807535 6…
Output: 1203429203

Example 2:

Input: 2776 723556 739977 399623 922083 989540 846684 108526 726116 862536 591467 801094 729834 319425 209299 345658 634619 689766 658442 349638 959876 546928 10120 761183 740028 490131 195105 271405 931858 599048 141786 842072 97964 970945 737735 815762 138556 118329 884731 154046 449902 519326 904488 557578 405049 833457 506473 368494 482886 27981 52030 448906 464478 857882 873799 506433 747973 419762 869020 260379 452755 274351 908835 144005 285564 573013 65339 98557 354512 100738 288501 366912 303926 759928 367932 747320 693645 604817 942181 700022 325011 443871 607438 586564 122301 15790 160777 684959 760746 873839 838115 134385 581887 738828 632220 763888 816194 275808 138833 25580 535976 316299 995834 124666 952900 866780 411476 143631 806774 289561 633198 413647 776357 951993 495613 42156…
Output: 1377098043

Example 3:

Input: 3042 883010 190858 477080 580376 301940 780889 257305 304437 561249 278023 434492 910587 895255 271147 159136 477430 848139 852714 164548 938785 914316 162798 531861 352405 241417 777231 148097 648930 889255 902833 841272 107944 193015 923364 248743 814425 316412 355524 176614 353735 504339 250481 50174 587809 299924 892300 210829 630406 858482 801311 96903 966654 663593 282202 842234 138776 864267 473777 53107 194568 725754 796375 869890 458036 424104 889193 600689 22261 757043 769708 93707 690511 189087 439062 64678 866967 248148 422711 146079 818438 674231 992437 264790 826362 263462 985906 509528 349846 817672 245327 598539 644558 80730 947463 313386 450595 314417 647609 871049 844548 182623 286637 829810 414883 601085 656504 48818 808344 220559 416627 427784 843739 803547 913559 21675…
Output: 1524396700

Constraints:

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

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