Submission #410245

#	Time	Username	Problem	Language	Result	Execution time	Memory
410245		ngpin04	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	855 ms	1048580 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;

vector <int> pos[3];

int dp[N][N][N][4];
int cost[N][N][N][4];
int n;

int solve(int i, int j, int k, int l, int pre) {
	int &res = dp[j][k][l][pre];
	if (i > n)
		return 0;
	if (res != -1)
		return res;
	res = 1e9;
	for (int val = 0; val < 3; val++) if (val != pre) {
		int newj = j + (val == 0);
		int newk = k + (val == 1);
		int newl = l + (val == 2);
		if (newj <= (int) pos[0].size() && newk <= (int) pos[1].size() && newl <= (int) pos[2].size()) {
			res = min(res, solve(i + 1, newj, newk, newl, val) + cost[j][k][l][val]);
		}
	}
	// cerr << i << " " << j << " " << k << " " << l << " " << pre << " " << res << "\n";
	return res;
}

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);
	}

	for (int i = 0; i < (int) pos[0].size(); i++) {
		int cur = pos[0][i];
		int add = 0;
		for (int j = 0; j <= (int) pos[1].size(); j++) {
			add += (j > 0 && pos[1][j - 1] > cur);
			int tmpadd = add;
			for (int k = 0; k <= (int) pos[2].size(); k++) {
				tmpadd += (k > 0 && pos[2][k - 1] > cur);
				cost[i][j][k][0] = (cur + tmpadd) - (i + j + k + 1);
			}
		}
	}

	for (int j = 0; j < (int) pos[1].size(); j++) {
		int cur = pos[1][j];
		int add = 0;
		for (int i = 0; i <= (int) pos[0].size(); i++) {
			add += (i > 0 && pos[0][i - 1] > cur);
			int tmpadd = add;
			for (int k = 0; k <= (int) pos[2].size(); k++) {
				tmpadd += (k > 0 && pos[2][k - 1] > cur);
				cost[i][j][k][1] = (cur + tmpadd) - (i + j + k + 1);
			}
		}
	}

	for (int k = 0; k < (int) pos[2].size(); k++) {
		int cur = pos[2][k];
		int add = 0;
		for (int j = 0; j <= (int) pos[1].size(); j++) {
			add += (j > 0 && pos[1][j - 1] > cur);
			int tmpadd = add;
			for (int i = 0; i <= (int) pos[0].size(); i++) {
				tmpadd += (i > 0 && pos[0][i - 1] > cur);
				cost[i][j][k][2] = (cur + tmpadd) - (i + j + k + 1);
			}
		}
	}

	memset(dp, -1, sizeof(dp));
	int ans = solve(1, 0, 0, 0, 3);
	if (ans == 1e9)
		ans = -1;
	cout << ans;
	return 0;
}

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