CT64186

Omkar's panels Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Omkar runs the fish market at the forest village of Briarthorn. Today the books show a list of panels, and the numbers must be worked out before sundown. 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 <= 2910; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2684 699513963 833043859 355014584 197093601 261868660 155839424 653336084 933639955 733235049 507425234 135301138 957894490 589280680 437946971 728025491 815017174 458585122 806373768 262520242 548515455 67482951 733084341 158405067 131788192 36476808 597371026 148755305 359724787 380456986 979323995 780556831 895107275 705577909 520634994 361213205 700511536 780833863 127145452 333246145 799764913 410802489 367726516 661573008 187292073 98527069 777512296 24116721 81709654 885003397 91529694 61786 773734161 467852178 738969648 325111723 847541850 519774584 123059436 150835960 235701177 229512799 966706486 183739915 699317972 959048765 541029425 917431942 265938329 398578937 248526252 584537463 826871451 525148765 958341692 709941276 47261654 875763620 475598458 154070516 501499507 660330…
Output: 1317803406732

Example 2:

Input: 1778 197323963 468785639 107113119 599918765 243614846 557429653 841025893 744818425 815306144 644971218 423973737 507676295 611295371 787838527 437494002 633892388 631382802 37495408 688564745 462076846 331778047 527118446 169181307 243479040 202580242 393324984 332241934 731639042 679897793 277392848 969947981 965212224 760371565 192066122 597576850 775751034 514515424 828132628 624422858 841352966 913434081 783975865 143789142 757955514 609133793 624015441 942145512 319742288 34185799 329936025 468948130 568658607 448120299 452415254 929332680 61296091 88963433 789702576 707092290 446801011 361668420 590448554 871789265 631760165 364753575 235434172 276801823 361779427 819900445 987684223 491277520 992481498 934872261 424939845 717706699 441748962 592760465 398886914 96058466 341208286 …
Output: 882656883618

Example 3:

Input: 1705 353303470 882481409 352997694 742077930 264697155 361197785 524215146 124451095 33231229 637191264 283671258 984316521 138231959 539261843 350521345 540684975 329718649 830635480 959649658 444460247 974730526 918847678 852945225 947666084 584472305 18515121 968677068 248741598 183967207 318277896 951855693 782122645 694650897 175841530 279872745 332995127 837787278 765058783 957284618 173419632 780291561 617469851 987087970 70425832 116542259 694052524 502561210 187256501 349010718 297889379 535801476 701117201 203885276 123759 667215754 665086215 795164497 164032108 448558531 387811082 201437439 255086162 292570827 624879326 359979567 299947801 642544086 190488403 583214384 899464285 126421275 849964059 513358165 265499864 67920043 852084190 26145482 898399185 94700085 906624419 4035…
Output: 829724015445

Constraints:

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

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