CT61089

Milo's Rustic Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Milo inherited the depot at the lantern reef of Glowtide along with its curious bookkeeping system for segments. 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 <= 775; 0 <= a[i] <= 1000000000.

Example 1:

Input: 570 818710090 660002533 72822100 481879131 395196241 385300846 524431060 346253233 326859851 730292174 407496652 779993099 136387181 832044131 564294609 205450297 956533729 724381952 761194395 228176034 149644384 908146615 201108308 949653170 676121875 808613228 360624985 923954266 717790497 80272730 172079503 723255984 672544302 760040135 943771558 650768456 400460974 283963255 725551467 310831197 193104581 15494938 164277364 958058648 618857375 508455808 231862446 782961034 644697478 595024565 854031806 251280483 385632162 683362461 546604189 873206890 304397067 773751109 451527779 580903892 568939191 396962343 289028733 651890875 911852084 259467955 181706199 78073012 755296949 317272143 241350510 686759401 859384365 40801324 830164578 532344430 324430938 778858586 406914855 244582180 5…
Output: 279267595256

Example 2:

Input: 289 164826532 693210457 12704314 363856240 469655253 419733798 241351557 170896613 86760047 752500241 900882695 689266827 976634170 879940279 829602930 911389904 380268204 929420383 666126306 483203419 58331098 705586962 742329730 35247579 1348683 616273703 787443775 887892069 774118471 951392322 160181806 535907542 491510570 99645590 299571868 29533584 101069404 814536282 644140867 70436965 577196443 545142442 168131713 141295287 636459124 713835200 82012837 903314464 112091274 316164858 323032478 239937867 729879799 291355846 650349707 535238607 230973012 508410973 593779407 1488558 840492544 886348201 934402865 932893224 259345953 48060792 23313482 248758711 173081211 832242051 534437451 777936748 994164034 939948970 987739000 760002420 988499876 344665305 299862963 767229170 142188964 …
Output: 132108831724

Example 3:

Input: 185 604409430 155147911 742319047 704104592 815176014 252916202 821272402 462990267 358570445 20799270 617100407 143818903 787848907 670137637 162713007 287254338 123844161 692310400 227609438 224462973 704168667 643929577 989939164 272328879 611348146 173954667 31125949 323857920 223983010 812713140 189162463 846864465 483730406 362236824 441127775 136015225 2696907 678044949 530835396 936617123 61355794 742871672 948388552 28841902 127692502 954214902 804385517 772282229 924299691 429306016 388734151 174452157 138832544 545931786 227337700 904468226 2030923 536992176 72848507 197198688 640498871 191143250 320196151 838798500 886151833 334080799 982582551 200639055 303256212 459701856 104504447 985865592 758374331 535579380 443656712 531910937 635031898 419380331 106791458 424631807 66425…
Output: 84317521403

Constraints:

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

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