Submission #375033

#	Time	Username	Problem	Language	Result	Execution time	Memory
375033		peijar	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	17 ms	6008 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;
		}
	}
	for (int deb(0); deb < N; ++deb)
		if (costJ[deb] < 1e18)
			costJ[deb] =  costJ[deb] - deb - 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;
		}
	}
	for (int fin(N-1); fin >= 0; --fin)
		if (costJ[fin] < 1e18)
		{
			costI[fin] += fin;
			if (fin < N-1)
				costI[fin] = min(costI[fin], costI[fin+1]);
		}
	int sol(1e18);
	for (int deb(0); deb < N-1; ++deb)
	{
		if (nbOcc[N-2] - 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;
		sol = min(sol, costJ[deb] + costI[fin]);
	}
	if (sol == 1e18)
		sol = -1;
	cout << sol << endl;
}

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