Submission #374997

#	Time	Username	Problem	Language	Result	Execution time	Memory
374997		peijar	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	2080 ms	5240 KiB

ho_t2

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

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

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;
		}
	}
	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;
		}
	}
	int sol(1e18);
	for (int deb(0); deb < N; ++deb)
		for (int fin(deb+1); fin < N; ++fin)
			if (nbOcc[fin-1] - nbOcc[deb] >= K)
				sol = min(sol, fin-deb-1-K + costJ[deb] + costI[fin]);
	if (sol == 1e18)
		sol = -1;
	cout << sol << endl;
}

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