CT43817

Petra's Ledger of scrolls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the thorn maze of Bramblecourt, Petra the factor keeps careful count of the scrolls. Plan the festival budget, every figure matters. 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 <= 2931; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2246 390632396 474125819 719350677 855962850 274804674 495336635 859090969 445197938 472303227 757074900 253993176 505098943 454014025 886984403 873111828 734312890 290026652 57866078 40567680 76641878 656465163 779193787 102214277 973249108 685514440 503657359 961959352 93907994 873400029 890844193 599446517 179023916 326330507 990059631 210251836 119875340 469945106 269543471 515399521 427304777 827893589 911120301 321993833 899028707 625205168 935217772 683214786 22042170 692688834 500287848 720037984 808759917 611205440 204819420 427213292 726638589 815353400 148897717 970099255 202495873 770051887 795390997 110617191 685771768 694528660 941533494 255083300 498514978 891771103 61125484 417780137 955688120 531853250 523528830 594339795 452545987 688623548 647192192 295172600 656528489 8…
Output: 1100901081712

Example 2:

Input: 1531 439786021 892252 972116664 944914494 35122722 26514669 645454207 292556681 294981287 623401261 918134168 686347549 421243378 30892245 433502274 615401957 24124675 141533628 461461729 224149901 375359692 116878806 288199208 297316132 498438504 878146442 90573739 470459497 923452401 336149807 586035035 641942592 500495916 296214638 955158391 140704334 405368676 14043376 901701270 709951350 196951217 690809891 168119831 650927300 935119937 231363372 124297426 719428660 586834983 487826520 509074195 353775612 981395826 612862142 529338339 893788786 200692557 221739493 206379329 474957186 518743308 69484201 914396860 857646844 580688616 274130176 760112272 787443176 424803175 914135520 50092333 542624429 999841069 400205354 726463986 728981830 383652337 153026033 303588406 42513758 1758418…
Output: 766493964753

Example 3:

Input: 1395 690192672 527916660 943961680 885849681 227852328 733750447 934692757 450443655 240274974 606119403 27839358 332645453 920650794 683314293 11368300 118063234 640619757 119808700 51430609 259248263 552248340 620530755 159321040 889044359 660845450 899861729 650353372 786643271 721048488 288330880 32393623 189665741 927299028 982113825 951948807 923792729 659453499 881292428 812501672 685897664 842426258 25748932 305500229 151556582 615954661 819072127 407101157 683427457 678987849 112673535 220900652 806672237 147325540 767612749 654875596 683674149 690700800 917221097 203578142 695560173 324041070 241426024 611249660 527352704 262684819 253315379 853745934 524838822 806467607 291610278 400443463 712969967 545909391 434094342 924926031 349228021 819160351 610878105 542930970 367261190 …
Output: 694269367639

Constraints:

1 <= n <= 2931; 0 <= a[i] <= 1000000000.

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