fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #pragma GCC optimize("Ofast")
  3. // #pragma GCC target("avx,avx2,fma")
  4. // #pragma GCC optimization("unroll-loops")
  5. // #pragma GCC optimize("unroll-loops")
  6. // #pragma GCC optimize("fast-math")
  7. // #pragma GCC optimize("no-stack-protector")
  8. // #define ll __int128
  9. #define ll long long
  10. // #define ll int
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define mod 1000000007
  13. // #define mod 998244353 
  14. #define mp make_pair
  15. #define uniq(v) (v).erase(unique(all(v)),(v).end())
  16. #define ff first
  17. #define ss second
  18. #define rf(i,a,b) for(int i=a;i>=b;i--)
  19. #define sc(a) scanf("%lld",&a)
  20. #define pf printf
  21. #define sz(a) (int)(a.size())
  22. #define psf push_front
  23. #define ppf pop_front
  24. #define ppb pop_back
  25. #define pb push_back
  26. #define pq priority_queue
  27. #define all(s) s.begin(),s.end()
  28. #define sp(a) setprecision(a)
  29. #define rz resize
  30. #define ld long double
  31. #define inf (ll)1e18
  32. #define ub upper_bound
  33. #define lb lower_bound
  34. #define bs binary_search
  35. #define eb emplace_back
  36. const double pi = acos(-1);
  37. ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
  38. // ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
  39.  
  40. using namespace std;
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.     // freopen("xortransform.in","r",stdin);
  47.     // freopen("xortransform.out","w",stdout);
  48. // #ifndef ONLINE_JUDGE
  49. //     freopen("input.txt","r",stdin);
  50. //     freopen("output.txt","w",stdout);
  51. // #endif
  52.     int z=1;
  53.     cin>>z;
  54.     f(i,1,z+1)
  55.     {
  56.         //cout<<"Case #"<<i<<": ";
  57.         ll n,K;
  58.         string s;
  59.         cin>>n>>K>>s;
  60.         vector<int> id;
  61.         f(i,0,sz(s))
  62.         {
  63.             if(s[i]=='1')
  64.                 id.pb(i);
  65.         }
  66.         int len=sz(id);
  67.         vector<vector<ll> > dp(len,vector<ll> (3,inf));
  68.         if(sz(id)==0)
  69.         {
  70.             cout<<"0\n";
  71.             continue;
  72.         }
  73.         if(id[0]-1<0)
  74.             dp[0][0]=inf;
  75.         dp[0][1]=dp[0][2]=1;
  76.         f(i,1,len)
  77.         {
  78.             f(j,0,3)
  79.             {
  80.                 ll deltar=j-1,nr=id[i]+deltar;
  81.                 f(k,0,3)
  82.                 {
  83.                     ll deltal=k-1,nl=id[i-1]+deltal;
  84.                     if(abs(nr-nl)<=K)
  85.                         dp[i][j]=min(dp[i][j],dp[i-1][k]);
  86.                     else
  87.                         dp[i][j]=min(dp[i][j],1+dp[i-1][k]);
  88.                 }
  89.             }
  90.         }
  91.         if(id[len-1]+1>=n)
  92.             dp[len-1][2]=inf;
  93.         ll ans=inf;
  94.         f(j,0,3)
  95.             ans=min(ans,dp[len-1][j]);
  96.         cout<<ans<<"\n";
  97.     }
  98. }
Success #stdin #stdout 0s 5496KB
comments (?)
stdin
copy 
3
6 2
010010
4 0
1001
7 2
1101001
stdout
copy 
1
2
1
https://ideone.com/wLzqs9
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!