Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define dim 1000009
  3. using namespace std;
  4. typedef long long ll;
  5. ll n,m,a,b;
  6. string s;
  7. ll p[dim];
  8. ll C[dim][3];
  9. ll func(ll x, ll c)
  10. {
  11.     if (x > n) return 0;
  12.     if (C[x][c] != 0) return C[x][c];
  13.  
  14.     if (c == 0)
  15.     {
  16.         if (x+a-1 > n) return 0;
  17.         return C[x][c] = a + func(x+a,1);
  18.     }
  19.     else
  20.     {
  21.         if (x+b-1 > n) return 0;
  22.         if (p[x+b-1] - p[x-1] < b) return 0;
  23.         return C[x][c] = b + func(x+b,0);
  24.     }
  25.     return C[x][c];
  26. }
  27. int main()
  28. {
  29.     cin>>n;
  30.     cin>>s;
  31.     s = " " + s;
  32.     cin>>m>>b>>a;
  33.     ll res = 0;
  34.     for (int i = 1; i <= n; i++)
  35.     {
  36.         p[i] = p[i-1];
  37.         if (s[i] == '1') p[i]++;
  38.     }
  39.     ll nd = m*(a+b);
  40.     for (int i = 1; i <= n-nd+1; i++)
  41.     {
  42.         res += (func(i,1) >= nd ? 1 :0);
  43.     }
  44.     cout<<res<<endl;
  45.     return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement