CT37980

Last ribbons of Ravi

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the ribbon falls of Cascade Vale. Ravi spreads the ribbons 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 <= 3816; 0 <= a[i] <= 1000000.

Example 1:

Input: 2055 81803 985324 495476 160039 651837 560831 165827 761138 696459 695691 283875 893437 842143 432085 427131 339199 70842 812803 922823 757473 503490 72212 185357 310402 187258 827639 587597 784555 864885 569497 567486 926324 898950 466289 949839 435939 561618 623788 471934 472114 599308 635078 508095 866843 10711 147283 706516 758442 819871 794927 330608 665002 592713 822516 727877 254378 756048 953405 15569 58803 595501 618441 503834 708194 295831 698483 282255 712633 855588 445007 495932 538923 599811 74909 283225 849121 651631 438198 942971 217796 59786 606252 995050 578442 225839 105668 160865 370679 604500 605598 542334 708424 823631 688336 666113 438595 849531 591354 518352 374460 618811 779759 895720 224929 951469 359347 564320 477276 521243 255576 356806 642503 957092 768119 30400…
Output: 1032144056

Example 2:

Input: 2399 470578 732976 779709 900704 811852 942776 233184 483843 782699 42864 417426 928869 374924 277420 189192 621357 723066 435593 336270 407745 588320 961688 302549 605852 544575 787214 296776 267979 856224 577835 378969 315940 963144 640785 13771 526465 718317 263729 117865 613124 886449 261582 600074 888359 100630 362968 160459 134942 111640 379437 301591 469308 957851 902804 197561 412213 682620 547432 463310 560045 959808 673924 451827 267523 727475 735013 220895 285216 996591 931280 512021 844273 757918 446293 526561 134580 571072 501464 798998 483878 959006 946577 131184 814746 441359 806757 451655 967 782779 297018 943714 572234 346665 681335 493659 370723 118661 537167 258585 140473 929981 478926 773670 505097 402213 857504 562740 651928 195849 189435 334563 682967 662456 943928 42…
Output: 1193607284

Example 3:

Input: 2434 325308 881268 634132 190612 10345 716670 469077 336394 400952 941669 141393 644352 865908 971505 226280 637092 275148 49702 887746 600688 165990 68833 920152 801888 159763 963129 717238 67183 166905 339107 243153 897323 697913 237464 147842 341173 95275 655397 736838 382367 178971 636145 506899 340641 470173 482480 518999 38121 506556 534989 945136 609080 373040 567349 49872 438986 635275 294075 128803 952268 522814 970501 696111 510949 310036 122588 222396 549456 976524 254792 995063 500270 168437 901028 462687 271090 663671 875366 490678 816439 163476 142917 375616 231210 319723 773206 44045 49683 252922 381542 543718 156583 871055 838546 875018 839266 495419 369283 358825 627938 59256 673132 316694 552854 410140 962918 374772 866494 503570 560653 68368 888551 580981 102130 967345 2…
Output: 1224424043

Constraints:

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

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