답안 #375006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375006	2021-03-08T20:40:56 Z	peijar	JJOOII 2 (JOI20_ho_t2)	C++17	1 / 100	1 ms	364 KB

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

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Incorrect	1 ms	364 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3

0 / 87.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	0 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Incorrect	1 ms	364 KB	Output isn't correct
29	Halted	0 ms	0 KB	-