CT63442

Hidden scrolls Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the orchid house of Bloomglass with crates of scrolls, and Lila the chronicler must account for every last one. 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 <= 2794; 0 <= a[i] <= 1000000.

Example 1:

Input: 2360 478475 639600 102350 864680 580014 986701 93125 748618 804716 657159 180155 838017 162056 806363 329163 471472 554459 601996 776726 178392 848101 309929 508126 890170 540624 770664 247407 442071 700613 225739 911455 983740 104013 915767 329308 595544 389791 782711 71192 270709 162176 778130 345096 270581 815949 835741 610635 103237 625369 155628 711919 417035 891160 184017 920101 488819 88017 403705 957493 418813 364205 358739 339792 449092 481311 147026 112653 717253 626973 677644 468534 525128 520662 400935 967009 764966 232925 322652 460329 351472 795369 282425 216261 57192 496157 847795 289298 264060 814106 232139 835950 119580 229022 328417 899460 837609 26493 761587 896809 352147 311824 607917 68297 369283 583770 268245 40909 347790 130440 64547 123142 38845 545346 819543 695934…
Output: 1147798573

Example 2:

Input: 67 274076 564704 394504 739182 603546 647429 978450 948396 227967 242608 198265 53777 772459 965389 476200 98258 323381 810575 426434 989636 801572 912662 53344 118000 582685 363937 50144 955286 40970 936857 134536 334481 772315 797098 499267 361477 132757 467934 289791 410195 614278 291060 466168 515792 297433 484228 501606 217348 244991 953814 15671 151464 470543 974795 548385 106234 223035 866572 907144 916772 202825 222274 768239 945590 160331 281709 79750
Output: 28394019

Example 3:

Input: 572 167734 66052 363782 851279 784176 389963 546271 382150 264601 318592 926277 615543 173004 971638 624147 585121 757588 17250 918174 874966 834006 649390 606652 990365 346520 3064 74068 17886 171200 243653 398360 386177 856664 726693 704312 276136 714617 352971 216248 833077 451120 327191 615579 353682 349875 714492 617776 746983 9059 992764 502739 837215 138065 376627 114585 588463 669056 168143 89503 858516 749230 300782 901821 331845 557593 34397 764883 678160 761033 199394 434224 437503 700133 499158 127926 705831 858570 639452 544741 192671 155329 963730 613390 823561 227673 218679 288168 166463 897345 373125 643581 807257 48769 910705 380796 385596 756297 731574 611741 57086 450568 354377 445031 705644 308297 518127 134643 523449 438205 780948 748457 919658 984185 373463 781435 449…
Output: 278762376

Constraints:

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

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