jakaria_hossain

codeforces - social distance

Jun 18th, 2020
1,241
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast()(ios_base::sync_with_stdio(0),cin.tie(NULL));
  4. #define pb push_back
  5. int main()
  6. {
  7.     fast()
  8.     int t;
  9.     cin>>t;
  10.     while(t--)
  11.     {
  12.         int n,k,ans=0,z=0;
  13.         cin>>n>>k;
  14.         string s;
  15.         cin>>s;
  16.         for(int i=0;i<n;i++)
  17.         {
  18.             if(s[i]=='0')z++;
  19.         }
  20.         if(z==n)
  21.         {
  22.             for(int i=0;i<n;i+=(k+1))ans++;
  23.             cout<<ans<<endl;
  24.         }
  25.         else if(z==0)cout<<ans<<endl;
  26.         else
  27.         {
  28.             vector<int>v;
  29.             //v.pb(0);
  30.             ans=0;
  31.             int i;
  32.             for(i=0;i<n;i++)if(s[i]=='1')
  33.             {
  34.                 v.pb(i);
  35.             }
  36.             bool f= false;
  37.             for(i=0;i<v[0];i+=k+1)
  38.             {
  39.                 ans++;
  40.                 f=true;
  41.             }
  42.             if(i>v[0] && f)ans--;
  43.             for( i=0;i<v.size()-1;i++)
  44.             {
  45.                f= false;
  46.                int j;
  47.                for( j=v[i]+k+1;j<v[i+1];j+=k+1)
  48.                {
  49.                    ans++;
  50.                    f=true;
  51.                }
  52.                if(j>v[i+1] && f)ans--;
  53.             }
  54.             for(i=v[v.size()-1]+k+1;i<n;i+=k+1)ans++;
  55.             cout<<ans<<endl;
  56.         }
  57.     }
  58. }
RAW Paste Data