Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long li;
- const li INF64 = li(1e18);
- int n, k;
- const int N = 400043;
- char buf[N];
- string s;
- li dp[N];
- int pos_next[N];
- int main()
- {
- scanf("%d %d", &n, &k);
- scanf("%s", buf);
- s = buf;
- for(int i = 0; i < n; i++) dp[i] = INF64;
- dp[n] = 0;
- int cur = 2 * n;
- for(int i = 0; i < n; i++)
- pos_next[i] = N;
- for(int i = n - 1; i >= -k; i--)
- {
- if(i >= 0 && s[i] == '1')
- cur = i;
- if(i + k < n)
- pos_next[i + k] = cur;
- }
- for(int i = n; i > 0; i--)
- {
- if(pos_next[i - 1] - (i - 1) <= k)
- {
- int nw = max(0, pos_next[i - 1] - k);
- dp[nw] = min(dp[nw], dp[i] + pos_next[i - 1] + 1);
- }
- dp[i - 1] = min(dp[i - 1], dp[i] + i);
- }
- printf("%lld\n", dp[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement