fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. #define ll long long int
  5. #define endl "\n"
  6. #define pb push_back
  7. #define mp make_pair
  8. #define ut unsigned int
  9. #define ss second
  10. #define ff first
  11. #define vi vector<int>
  12. #define vl vector<ll>
  13. #define lb lower_bound
  14. #define up upper_bound
  15. #define re return 
  16. #define yes cout<<"YES"<<endl
  17. #define no cout<<"NO"<<endl
  18.  
  19.  
  20. int main()
  21. {
  22. int t ;
  23. cin >> t;
  24. while(t--) 
  25. {
  26.   ll n,k,cnt1=0,cnt0=0,f=0,i,a=0,b=0;
  27.   cin>>n>>k;
  28.   string s;
  29.   cin>>s;
  30.   vi v;
  31.  
  32.   for(i=0;i<n;i++){
  33.   	if(s[i]=='0'){
  34.   	a++;
  35.   	}
  36.   	else
  37.   	break;
  38.   }
  39.   for(i=n-1;i>=0;i--){
  40.   	if(s[i]=='0'){
  41.   	b++;
  42.     }
  43.   	else
  44.   	break;
  45.   }
  46.  
  47.   for(i=0;i<n;i++){
  48.   	if(s[i]=='0'){
  49.   	cnt0++;
  50.   	cnt1++;
  51.   	}
  52.   	else
  53.   	{
  54.   		v.pb(cnt0);
  55.   		cnt0=0;
  56.   	}
  57.   }
  58.   if(cnt0>0)
  59.   v.pb(cnt0);
  60.   sort(v.begin(),v.end());
  61.   ll r=v.size(),s1=0,flag=0,temp=0;;
  62.   for(i=0;i<r;i++)
  63.   s1=s1+v[i];
  64.   if(n==1)
  65.   cout<<"0";
  66.   else if(cnt1==n || cnt1==0)
  67.   cout<<"0";
  68.   else{
  69.   i=0;
  70.    while(k>0){
  71.    	s1=s1-v[r-1-i];
  72.    	if(k==1){
  73.    		if(flag==1 && temp==1)
  74.    		break;
  75.    		else if(flag==0 && temp==0){
  76.    			s1=s1+v[r-1-i];
  77.    			s1=s1-max(a,b);
  78.    			break;
  79.    		}
  80.    		else if(flag==0){
  81.    			s1=s1+v[r-1-i];
  82.    			s1=s1-a;
  83.    			break;
  84.    		}
  85.    		else if(temp==0)
  86.    		{
  87.    			s1=s1+v[r-1-i];
  88.    			s1=s1-b;
  89.    			break;
  90.    		}
  91.    	}
  92.    	else if(v[r-1-i]==a && flag==0){
  93.    		k--;
  94.    		flag=1;
  95.    	}
  96.    	else if(v[r-1-i]==b && temp==0){
  97.    		k--;
  98.    		temp=1;
  99.    	}
  100.    	else 
  101.    	k=k-2;
  102.    	i++;
  103.    }
  104.    if(s1<0)
  105.    s1=0;
  106.    cout<<s1<<" ";
  107.   }
  108.   cout<<endl;
  109. }  
  110. return 0;
  111. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
2
4 0
1000
10 3
0101010111
stdout
copy 
3 
2
https://ideone.com/ou7MPA
language:
C++14 (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!