Submission #288755

#	Time	Username	Problem	Language	Result	Execution time	Memory
288755		luciocf	JJOOII 2 (JOI20_ho_t2)	C++14	13 / 100	218 ms	217224 KiB

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 / 1
• Subtask 2: 12 / 12
• Subtask 3: 0 / 87