CT55120

The Hidden Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morgana inherited the studio at the sulphur springs of Brimstone along with its curious bookkeeping system for windows. Time to make sense of it. 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 <= 1106; 0 <= a[i] <= 1000000000.

Example 1:

Input: 607 247539931 768246104 653405019 970794229 329193358 651535963 657014574 781500684 444635845 729330110 405083598 667276983 72112507 478311550 21424819 482677826 389075212 429225005 298185247 150697309 593458211 343600776 701193117 417695692 17564356 497416399 168410030 256856704 333630543 385280044 892022766 653974549 530551649 707746953 583730347 250913271 603971792 875103304 812152697 801525852 367586181 576579128 945671164 400375528 45004472 706677871 409289125 515684716 627409639 829392900 612814104 946160827 692204578 545662755 403093547 453365186 490912532 410546767 150468008 139224501 276071474 973926921 975787623 79002986 31274388 416281024 80285880 789326313 472416865 526735969 696448933 136887288 649958110 572844617 421458567 329828054 144138023 154231362 49283003 492021150 5005…
Output: 303814202653

Example 2:

Input: 1000 909531510 566815786 570289302 153120061 245533684 953464681 542846383 19338164 330809775 539391800 235614166 979812901 246327458 259778148 288393366 769088362 89144506 153310569 639084454 661063130 43389599 630809465 424339511 182361530 885539241 730155432 884348560 199530346 53550025 282672075 584431556 734653010 94195771 635436229 708589137 91667806 972018971 972696638 804825914 608756535 513397854 491359758 705265429 396194958 537933364 937230214 484302284 498342886 208104156 520886262 181841963 241687951 945503330 798252509 283223561 936065836 686513129 585486454 29891708 902845119 771825065 686610288 133084427 66177410 288425148 899003872 994048413 554422042 227705018 385805114 699758033 135067189 875042342 336020555 696004323 769219897 2417876 808188994 240104114 494604393 21573…
Output: 495999795963

Example 3:

Input: 139 744808302 478723720 270547341 251126528 108855923 669522667 935368843 737082010 847624099 506071623 607787789 473222735 654853375 347209713 6190645 668814951 295519847 136636537 130401897 823512396 411924280 415908989 937137468 50061534 448958660 472580948 283151400 804632883 504537342 931414719 242471283 445106767 723221411 588736011 955440060 415035008 702378227 392407273 555106125 87294278 874871955 292741737 235540120 386886391 955805564 541083625 856807259 107996235 180236912 995718329 962492898 519246070 880789388 180049568 498315073 921686831 225228660 304241638 811421069 265889456 477334638 566129197 213501613 349761502 107279894 942374804 725039217 698294406 774329978 664723698 993281835 523012770 12543694 605733908 203919947 292689977 113456015 504390249 331926712 47411132 34…
Output: 54225181295

Constraints:

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

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