CT50024

Miller's Ledger of stretches

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the saffron fields of Marigold Row. Miller spreads the stretches records across the table and picks up a sharp pencil. 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 <= 1005; 0 <= a[i] <= 1000000.

Example 1:

Input: 597 862972 526415 626225 151228 284273 575960 451146 273624 645222 908477 222139 634028 888077 282020 568588 570287 782995 247756 862335 983209 830393 946949 57297 549770 693452 837009 158964 42327 74794 682865 316304 278025 830605 736662 30919 662500 564119 759070 837252 386 51902 945184 970785 681025 633108 533391 213454 251722 941850 611718 237058 873415 774908 560742 312643 820451 62574 652591 383578 36516 729305 365655 811940 652330 265340 463020 257625 281365 773609 1928 288123 82635 436443 817774 653732 1402 738715 303308 357187 501597 695462 785905 456006 338248 385571 41135 953468 450540 898848 380605 405089 376781 401242 151428 21061 865857 502938 769233 902999 148550 130921 819478 841603 588840 167301 580229 338405 663051 391708 737011 294023 360082 434720 400903 305912 560535 8…
Output: 282373246

Example 2:

Input: 679 558468 508316 506221 355832 704528 513911 342752 369175 800917 803418 72044 771889 217642 876858 904208 460788 612774 365827 709669 95545 930319 371259 732949 907527 760585 494903 383107 901814 700665 888981 519518 23870 659394 176599 868332 47473 660389 237783 194294 786602 988819 941413 603748 41591 751424 246478 447128 691441 638281 933670 154410 347977 563910 696385 290390 86283 113523 474276 211781 813692 138276 729550 117328 924970 737389 291766 479043 525246 797362 696406 833926 265399 557312 665889 920468 763498 123254 859903 762554 912975 465928 63074 701838 839169 42477 767661 587064 489604 186457 952915 702093 139676 332322 823123 799698 376089 968738 562385 274818 436059 555568 683039 379271 98305 140245 205886 392919 119011 206744 327234 292674 483930 310455 365874 944860 …
Output: 304181249

Example 3:

Input: 502 794654 171526 276868 795926 466547 583946 658672 467430 681200 169193 830876 692333 470238 555615 271808 878156 471434 707734 360022 842052 73625 568310 815186 153231 28488 97492 225360 965764 749340 441864 401616 899418 722600 942304 711898 250895 867770 771772 533162 16052 814423 474024 471614 767885 159911 642379 893518 767466 236078 837754 331796 41313 840083 301151 671761 54112 382543 500877 988679 854594 199537 524238 817723 990885 534950 617458 120723 887063 520628 917740 457769 49340 95357 982045 415955 315342 509882 262298 593782 315292 373048 144466 322374 334620 792323 581797 204532 318055 305682 807249 102600 717107 418415 857504 856453 787550 307841 6589 213963 733594 476770 824091 629215 501002 54251 911494 260417 523248 672517 557626 319958 413010 124412 684899 395599 83…
Output: 236864515

Constraints:

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

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