Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
1,772
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long li;
  6. const li INF64 = li(1e18);
  7.  
  8. int n, k;
  9. const int N = 400043;
  10. char buf[N];
  11. string s;
  12.  
  13. li dp[N];
  14. int pos_next[N];
  15.  
  16. int main()
  17. {
  18. scanf("%d %d", &n, &k);
  19. scanf("%s", buf);
  20. s = buf;
  21. for(int i = 0; i < n; i++) dp[i] = INF64;
  22. dp[n] = 0;
  23. int cur = 2 * n;
  24. for(int i = 0; i < n; i++)
  25. pos_next[i] = N;
  26. for(int i = n - 1; i >= -k; i--)
  27. {
  28. if(i >= 0 && s[i] == '1')
  29. cur = i;
  30. if(i + k < n)
  31. pos_next[i + k] = cur;
  32. }
  33. for(int i = n; i > 0; i--)
  34. {
  35. if(pos_next[i - 1] - (i - 1) <= k)
  36. {
  37. int nw = max(0, pos_next[i - 1] - k);
  38. dp[nw] = min(dp[nw], dp[i] + pos_next[i - 1] + 1);
  39. }
  40. dp[i - 1] = min(dp[i - 1], dp[i] + i);
  41. }
  42. printf("%lld\n", dp[0]);
  43. return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement