Submission #375005

#	Time	Username	Problem	Language	Result	Execution time	Memory
375005		peijar	JJOOII 2 (JOI20_ho_t2)	C++17	1 / 100	1 ms	512 KiB

ho_t2

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

// costJ(i), costI(i)
// sol = min_{i, j} (costJ[i] -i - K) + (costI[j]  + j-1)

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int N, K;
	string s;
	cin >> N >> K >> s;
	vector<int> costJ(N, 1e18), costI(N, 1e18);
	vector<int> nbOcc(N);
	for (int i(0); i < N; ++i)
	{
		if (i) nbOcc[i] += nbOcc[i-1];
		nbOcc[i] += s[i] == 'O';
	}
	queue<int> q;
	for (int i(0); i < N; ++i)
	{
		if (s[i] == 'J')
			q.push(i);
		while ((int)q.size() > K) q.pop();
		if ((int)q.size() == K)
		{
			int lst = q.front();
			costJ[i] = (i - lst +1 - K) - i - K;
		}
	}
	while (!q.empty()) q.pop();
	for (int i(N-1); i >= 0; --i)
	{
		if (s[i] == 'I')
			q.push(i);
		while ((int)q.size() > K) q.pop();
		if ((int)q.size() == K)
		{
			int lst = q.front();
			costI[i] = (lst - i + 1 - K) + i - 1;
		}
		if (i < N-1)
			costI[i]= min(costI[i], costI[i+1]);
	}

	int sol(1e18);
	for (int deb(0); deb < N; ++deb)
	{
		if (nbOcc[N-1] - nbOcc[deb] < K)
			continue;
		int lo(deb+1), up(N-1);
		while (lo < up)
		{
			int mid = (lo + up) / 2;
			if (nbOcc[mid-1] - nbOcc[deb] < K)
				lo = mid+1;
			else
				up = mid;
		}
		int fin = lo;
		if (fin < N)
			sol = min(sol, costJ[deb] + costI[fin]);
	}
	if (sol == 1e18)
		sol = -1;
	cout << sol << endl;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87