fork download
copy 
  1.     #include<bits/stdc++.h>
  2.     using namespace std;
  3.     typedef long long ll;
  4.     #define flow ios_base::sync_with_stdio(false);cin.tie(NULL);
  5.     int n,k,dp[1000001][2],*a;
  6.     string s;
  7.     int pre_sum(int l,int r)
  8.     {
  9.         if(r<0)return 0;
  10.         if(r>=n)r=n-1;
  11.         return a[r]-((l-1>=0)?a[l-1]:0);
  12.     }
  13.     int fn(int pos,int off)
  14.     {
  15.         if(pos>=n)return 0;
  16.         if(dp[pos][off]!=-1)return dp[pos][off];
  17.         int ans1=pre_sum(pos+1,pos+k-1);
  18.         if(!off)
  19.             {
  20.                 if(s[pos]=='0')ans1+=min(1+fn(pos+k,0),fn(pos+k,1));
  21.                 else ans1+=min(fn(pos+k,0),1+fn(pos+k,1));
  22.             }
  23.         else
  24.             {
  25.                 if(s[pos]=='0')ans1+=fn(pos+k,1);
  26.                 else ans1+=1+fn(pos+k,1);
  27.             }
  28.         return (dp[pos][off]=ans1);
  29.     }
  30.     int main()
  31.     {
  32.         flow;
  33.         int t;cin>>t;
  34.         while(t--)
  35.         {
  36.             cin>>n>>k>>s;
  37.             a=new int[n];
  38.             for(int i=0;i<n;i++)
  39.             {   dp[i][0]=dp[i][1]=-1;
  40.                 a[i]=0;
  41.             }
  42.             a[0]=((s[0]=='1')?1:0);
  43.             for(int i=1;i<n;i++)
  44.                 {
  45.                     if(s[i]=='1')a[i]=1+a[i-1];
  46.                     else a[i]=a[i-1];
  47.                 }
  48.             int ans=INT_MAX;
  49.             for(int i=0;i<n;i++)
  50.                 if(s[i]=='1')ans=min(ans,pre_sum(0,i-1)+fn(i,0));
  51.             cout<<((ans==INT_MAX)?0:ans)<<endl;
  52.         }
  53.     	return 0;
  54.     }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0
stdout
copy 
1
2
5
4
0
0
https://ideone.com/lrUG1a
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

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!