CT62158

Steward and the Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the rook towers of Chessfield as Steward unrolls the day's manifest of scrolls. The tally will decide the next shipment. 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 <= 1277; 0 <= a[i] <= 1000000000.

Example 1:

Input: 599 183401425 379311119 897415742 965057697 605440573 87009238 381818349 214214630 103546324 696346341 629648438 520197678 568866981 25918565 70416966 927944275 178859110 170423209 43377888 738942952 419178424 899260546 50217161 967599109 54523152 115810374 211601283 822864932 226243112 459884108 163118218 600052597 37252357 634475739 571535806 756384554 953302574 148240913 701237974 690347638 490477704 697335924 907430905 251473803 30734774 968994874 502263234 978895024 325646617 215302833 849810905 196526113 746024531 128434311 527474714 272987787 98675963 319462751 650414322 201849065 991444445 120710898 94763905 421414274 470663282 512363498 669734920 155310560 452713718 853910716 922814540 18657142 781812849 279263017 935629719 254130974 769587125 153069900 549965223 945162465 5765512…
Output: 286744894933

Example 2:

Input: 161 743715460 954914910 900281443 466650805 473743143 188946539 933311229 973462303 358414864 879453374 680364034 959970543 36106236 983433954 759507499 831015533 770622092 407385761 514186991 157101691 193314531 50060005 237919151 298122967 377761077 689956201 766070535 244630902 239739295 170779090 881904017 515658913 812858744 424688559 69813446 89346138 739142292 821019102 780241206 788803157 139954239 767696850 301264124 365232202 942305402 340755739 649492589 770758217 20223970 660748556 274112312 284110909 761895015 871881814 407697150 737204563 324454229 10616292 846439055 204722568 752203618 753007300 231122640 62867318 846936440 349618331 262973758 129225419 570177171 17152114 808859964 659814549 309048935 532533658 47789380 159816948 68189907 894924502 756274915 41056903 3124285…
Output: 74599476953

Example 3:

Input: 669 779931632 650461110 562645335 197870022 809281505 924035917 833165655 948275250 454918027 302933229 977425802 381011689 940782855 249162121 339264095 168441422 445315802 568522851 645834677 450553466 504064272 897252998 528218 756168979 676468722 333457793 601168146 490207844 680436913 487478591 93453434 340149575 948765992 114362167 301850943 476516519 513804926 847175889 249212261 69853381 829687918 793912137 517696342 239821564 535179336 640922990 205130652 367500709 844571826 520667940 923555626 141205088 998692957 116978247 30115693 112836529 685162924 882479254 502130380 943575012 980953152 133164395 402851057 870708864 599369758 644132985 59383350 26685823 494695679 128240596 722106933 186184080 45629458 457711088 739497296 40947241 309781571 422057950 115552270 594831376 852316…
Output: 331581699527

Constraints:

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

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