Submission #410257

#	Time	Username	Problem	Language	Result	Execution time	Memory
410257		ngpin04	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	97 ms	162912 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 405;
const int oo = 1e9;

vector <int> pos[3];

int dp[N][N][N][4];
int cnt[N][3];
int sz[3];
int n;

template <typename T> 
void mini(T &a, T b) {
	if (a > b)
		a = b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char c; cin >> c;
		int val = 2;
		if (c == 'R')
			val = 0;
		if (c == 'G')
			val = 1;
		pos[val].push_back(i);
		cnt[i][val]++;
	}

	for (int i = 1; i <= n; i++)
	for (int j = 0; j < 3; j++)
		cnt[i][j] += cnt[i - 1][j];

	for (int i = 0; i < 3; i++)
		sz[i] = pos[i].size();
	
	for (int i = 0; i <= sz[0]; i++) 
	for (int j = 0; j <= sz[1]; j++)
	for (int k = 0; k <= sz[2]; k++)
	for (int pre = 0; pre < 3; pre++) 
		if (i || j || k)
			dp[i][j][k][pre] = oo;

	for (int i = 0; i <= sz[0]; i++)
	for (int j = 0; j <= sz[1]; j++)
	for (int k = 0; k <= sz[2]; k++)
	for (int pre = 0; pre < 3; pre++) if (dp[i][j][k][pre] < oo) {
		int cur = dp[i][j][k][pre];
		int x = i + j + k + 1;
		if (i < sz[0] && pre != 0) {
			int posval = pos[0][i];
			if (j > 0) 
				posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[0][i]][1]);
			if (k > 0)
				posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[0][i]][2]);
			mini(dp[i + 1][j][k][0], cur + posval - x);
		}

		if (j < sz[1] && pre != 1) {
			int posval = pos[1][j];
			if (i > 0) 
				posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[1][j]][0]);
			if (k > 0)
				posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[1][j]][2]);
			mini(dp[i][j + 1][k][1], cur + posval - x);
		}

		if (k < sz[2] && pre != 2) {
			int posval = pos[2][k];
			if (j > 0) 
				posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[2][k]][1]);
			if (i > 0)
				posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[2][k]][0]);
			mini(dp[i][j][k + 1][2], cur + posval - x);
		}
	}
	int ans = oo;
	for (int i = 0; i < 3; i++)
		ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
	if (ans == oo)
		ans = -1;
	cout << ans;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25