Submission #288755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
288755	2020-09-01T21:02:20 Z	luciocf	JJOOII 2 (JOI20_ho_t2)	C++14	13 / 100	218 ms	217224 KB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e3+10;
const int inf = 1e9+10;

int n, k;
string a;

int dp[maxn][maxn][3];

int solve(int i, int j, int q)
{
	if (q == 2 && j == k) return 0;
	if (i == n) return inf;
	if (dp[i][j][q] != -1) return dp[i][j][q];

	int ans = inf;

	if (q == 0 && j == 0) ans = min(ans, solve(i+1, 0, 0));

	if (q == 0)
	{
		ans = min(ans, 1+solve(i+1, j, q));

		if (a[i] == 'J')
		{
			if (j+1 < k) ans = min(ans, solve(i+1, j+1, q));
			else ans = min(ans, solve(i+1, 0, 1));
		}
	}
	else if (q == 1)
	{
		ans = min(ans, 1+solve(i+1, j, q));

		if (a[i] == 'O')
		{
			if (j+1 < k) ans = min(ans, solve(i+1, j+1, q));
			else ans = min(ans, solve(i+1, 0, 2));
		}
	}
	else
	{
		ans = min(ans, 1+solve(i+1, j, q));

		if (a[i] == 'I')
			ans = min(ans, solve(i+1, j+1, q));
	}

	return dp[i][j][q] = ans;
}

int main(void)
{
	cin >> n >> k >> a;

	memset(dp, -1, sizeof dp);

	int ans = solve(0, 0, 0);

	if (ans == inf) cout << "-1\n";
	else cout << ans << "\n";
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	106748 KB	Output is correct
2	Correct	58 ms	106744 KB	Output is correct
3	Correct	58 ms	106744 KB	Output is correct
4	Correct	58 ms	106744 KB	Output is correct
5	Correct	58 ms	106744 KB	Output is correct
6	Correct	59 ms	106744 KB	Output is correct
7	Correct	59 ms	106744 KB	Output is correct
8	Correct	58 ms	106744 KB	Output is correct
9	Correct	58 ms	106744 KB	Output is correct
10	Correct	59 ms	106744 KB	Output is correct
11	Correct	58 ms	106744 KB	Output is correct
12	Correct	59 ms	106744 KB	Output is correct
13	Correct	58 ms	106744 KB	Output is correct
14	Correct	58 ms	106872 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	106748 KB	Output is correct
2	Correct	58 ms	106744 KB	Output is correct
3	Correct	58 ms	106744 KB	Output is correct
4	Correct	58 ms	106744 KB	Output is correct
5	Correct	58 ms	106744 KB	Output is correct
6	Correct	59 ms	106744 KB	Output is correct
7	Correct	59 ms	106744 KB	Output is correct
8	Correct	58 ms	106744 KB	Output is correct
9	Correct	58 ms	106744 KB	Output is correct
10	Correct	59 ms	106744 KB	Output is correct
11	Correct	58 ms	106744 KB	Output is correct
12	Correct	59 ms	106744 KB	Output is correct
13	Correct	58 ms	106744 KB	Output is correct
14	Correct	58 ms	106872 KB	Output is correct
15	Correct	58 ms	106872 KB	Output is correct
16	Correct	57 ms	106872 KB	Output is correct
17	Correct	59 ms	106872 KB	Output is correct
18	Correct	70 ms	106744 KB	Output is correct
19	Correct	64 ms	106872 KB	Output is correct
20	Correct	65 ms	106792 KB	Output is correct
21	Correct	94 ms	106872 KB	Output is correct
22	Correct	95 ms	106872 KB	Output is correct
23	Correct	73 ms	106744 KB	Output is correct
24	Correct	96 ms	106872 KB	Output is correct
25	Correct	100 ms	106872 KB	Output is correct
26	Correct	97 ms	106872 KB	Output is correct
27	Correct	98 ms	106872 KB	Output is correct
28	Correct	95 ms	106872 KB	Output is correct
29	Correct	98 ms	106872 KB	Output is correct
30	Correct	99 ms	106872 KB	Output is correct
31	Correct	65 ms	106744 KB	Output is correct
32	Correct	100 ms	106876 KB	Output is correct
33	Correct	58 ms	106888 KB	Output is correct
34	Correct	91 ms	106892 KB	Output is correct
35	Correct	164 ms	106876 KB	Output is correct

Subtask #3

0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	106748 KB	Output is correct
2	Correct	58 ms	106744 KB	Output is correct
3	Correct	58 ms	106744 KB	Output is correct
4	Correct	58 ms	106744 KB	Output is correct
5	Correct	58 ms	106744 KB	Output is correct
6	Correct	59 ms	106744 KB	Output is correct
7	Correct	59 ms	106744 KB	Output is correct
8	Correct	58 ms	106744 KB	Output is correct
9	Correct	58 ms	106744 KB	Output is correct
10	Correct	59 ms	106744 KB	Output is correct
11	Correct	58 ms	106744 KB	Output is correct
12	Correct	59 ms	106744 KB	Output is correct
13	Correct	58 ms	106744 KB	Output is correct
14	Correct	58 ms	106872 KB	Output is correct
15	Correct	58 ms	106872 KB	Output is correct
16	Correct	57 ms	106872 KB	Output is correct
17	Correct	59 ms	106872 KB	Output is correct
18	Correct	70 ms	106744 KB	Output is correct
19	Correct	64 ms	106872 KB	Output is correct
20	Correct	65 ms	106792 KB	Output is correct
21	Correct	94 ms	106872 KB	Output is correct
22	Correct	95 ms	106872 KB	Output is correct
23	Correct	73 ms	106744 KB	Output is correct
24	Correct	96 ms	106872 KB	Output is correct
25	Correct	100 ms	106872 KB	Output is correct
26	Correct	97 ms	106872 KB	Output is correct
27	Correct	98 ms	106872 KB	Output is correct
28	Correct	95 ms	106872 KB	Output is correct
29	Correct	98 ms	106872 KB	Output is correct
30	Correct	99 ms	106872 KB	Output is correct
31	Correct	65 ms	106744 KB	Output is correct
32	Correct	100 ms	106876 KB	Output is correct
33	Correct	58 ms	106888 KB	Output is correct
34	Correct	91 ms	106892 KB	Output is correct
35	Correct	164 ms	106876 KB	Output is correct
36	Correct	66 ms	107272 KB	Output is correct
37	Correct	67 ms	107400 KB	Output is correct
38	Correct	69 ms	107400 KB	Output is correct
39	Runtime error	218 ms	217224 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-