제출 #288755

#제출 시각아이디문제언어결과실행 시간메모리
288755luciocfJJOOII 2 (JOI20_ho_t2)C++14
13 / 100
218 ms217224 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...