Please help finding the bug. Here’s the commented code
PS- Thanks in advance
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#pragma GCC optimization (“unroll-loops”
#pragma GCC optimize “trapv”
#define _GLIBCXX_DEBUG
#define ll long long int
#define ld long double
#define ull unsigned long long int // ranges from (0 - twice of long long int)
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i–)
#define pb push_back
#define mp make_pair
#define vll vector
#define MOD 1000000007LL
#define llpair pair<ll,ll>
#define INF 1000000000000000000ll // this is 1e18 long long
#define np next_permutation
#define PI acos(-1)
#define DEB(x) cout<<#x<<" "<<x<<endl;
#define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
#define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
int main()
{
speed;
ll t=1;
cin>>t;
while(t–)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
vectorone,two; // one stores the length of 0s block which reuire 1 cut
// similarly for two
ll start=-1,finish=n,cnt=0; // start - index for first occurence of 1
// finish - index for occurence of 1 from last
rep(i,0,n)
cnt+=(s[i]=='0'); // count no of 0
if(cnt==n)
{
cout<<0<<endl;
continue;
}
rep(i,0,n)
{
while(s[i]=='0')
{
i++; // finding the index and also the length of block of 0 from starting
start=i;
}
break;
}
per(i,0,n)
{
while(s[i]=='0') //// finding the index and also the length of block of 0 from starting
{
i--;
finish=i;
}
break;
}
if(start!=-1)
one.pb(start); // storing in one
if(finish!=n)
one.pb(n-finish-1); // storing in one
else
{
finish--;
}
sort(one.begin(),one.end(),greater<ll>()); // sort in descending
for(ll i=start;i<=finish;i++)
{
ll len=0;
while( i<=finish && s[i]=='0') // finding blocks of 0 which require 2 cuts
{
i++;
len++;
}
// DEB(len);
if(len!=0)
two.pb(len);
}
sort(two.begin(),two.end(),greater<ll>()); //sort in desc
if(k==0)
{
cout<<cnt<<endl; // if k==0
}
ll ans=0,size=two.size(); // ans stores the maximum zeroes that can be removed using cuts
if(one.size()>0 && k>0)
{
ll temp=one[0]; // in each if block finding max ans for it
ll also=k-1;
rep(i,0,min(size,also/2)) // also stores the updated value of k
{ // we can take atmost max(two.size(),also/2) elements
temp+=two[i];
}
ans=max(ans,temp);
}
if (one.size()>1 && k>1 )
{
ll temp=one[0]+one[1];
ll also=k-2;
rep(i,0,min(size,also/2)) // similar as above for scenario when k>1 and one.size()>1
{
temp+=two[i];
}
ans=max(ans,temp);
}
if(k>=2)
{ // finally checking if we can obtain the max value by removing only 2 cut requiring elements
ll t1=0;
rep(i,0,min(size,k/2))
{
t1+=two[i];
}
ans=max(ans,t1);
}
cnt-=min(cnt,ans);
cout<<cnt<<endl;
}
return 0;
}
