MAXVAC - Editorial

editorial
, ,
2

I calculated the longest subarray such that there is only a single ‘1’ in it.
After that I flipped the ‘1’ to ‘0’.
And then I found the contiguous segments of 0’s in the modified string and incremented the answer accordingly , i.e if the segment contains A zeros , then ans+=A/X;

Plz tell why this is wrong

#include <bits/stdc++.h>
#define int long long int
using namespace std;

void solve()
{
	int n, x;
	cin >> n >> x;
	string str;
	cin >> str;
	int zero_count = 0;
	int i = 0, j = 0, cnt = 0, ans = 0;
	int final = 0;
	int left;
	int right;
	//longest subarray having at most one '1' => str[left...right]
	for (; j < n; ++j) {
		cnt += str[j] == '1';
		while (cnt > 1) cnt -= str[i++] == '1';
		if ((j - i + 1) > ans)
		{
			left = i;
			right = j;
			ans = max(ans, j - i + 1);
		}
	}
	for (int i = left; i <= right; ++i)
	{
		if (str[i] == '1')
		{str[i] = '0'; break;}
	}
	for (int i = 0; i < n; ++i)
	{
		if (str[i] == '0')
			zero_count++;
		else
		{
			final += (zero_count / x);
			zero_count = 0;
		}
	}
	if (str[n - 1] != '1')
		final += (zero_count / x);
	cout << final << endl;


}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int tc = 1;
	cin >> tc;
	while (tc--)
	{
		solve();
	}

}
1 Like