Submission #163279

#	Time	Username	Problem	Language	Result	Execution time	Memory
163279		iefnah06	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	89 ms	4216 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

void setmin(int& a, int b) {
	if (a > b) {
		a = b;
	}
}

const int INF = 1e9;

const int MAXN = 405;
int N;
char S[MAXN];

vector<int> locs[3];
int g[3][MAXN][3];

int dp[2][MAXN][MAXN][3];

map<char, int> mp = {
	{'R', 0},
	{'G', 1},
	{'Y', 2}
};

int get_cost(int a, int b, int c, int x, int p) {
	return max(0, a - g[x][p][0]) + 
			max(0, b - g[x][p][1]) + 
			max(0, c - g[x][p][2]);
}

int main() {
	scanf("%d", &N);
	scanf("%s", S);
	for (int i = 0; i < N; i++) {
		locs[mp[S[i]]].push_back(i);
	}

	for (int a = 0; a < 3; a++) {
		int tmp[3] = {};
		for (int i = 0; i < int(locs[a].size()); i++) {
			for (int b = 0; b < 3; b++) {
				while (tmp[b] < int(locs[b].size()) && locs[b][tmp[b]] < locs[a][i]) {
					tmp[b]++;
				}
				g[a][i][b] = tmp[b];
			}
		}
	}

	int cur = 0, nxt = 1;
	dp[cur][0][0][0] = 0;
	dp[cur][0][0][1] = dp[cur][0][0][2] = INF;
	for (int n = 0; n < N; n++, swap(cur, nxt)) {
		for (int a = 0; a <= n + 1; a++) {
			for (int b = 0; a + b <= n + 1; b++) {
				fill_n(dp[nxt][a][b], 3, INF);
			}
		}

		for (int a = 0; a <= n; a++) {
			for (int b = 0; a + b <= n; b++) {
				int c = n - a - b;
				for (int x = 0; x < 3; x++) {
					if (dp[cur][a][b][x] == INF) continue;
					if ((a + b == 0 || x != 0) && a < int(locs[0].size())) {
						setmin(dp[nxt][a + 1][b][0], dp[cur][a][b][x] + get_cost(a, b, c, 0, a));
					}
					if (x != 1 && b < int(locs[1].size())) {
						setmin(dp[nxt][a][b + 1][1], dp[cur][a][b][x] + get_cost(a, b, c, 1, b));
					}
					if (x != 2 && c < int(locs[2].size())) {
						setmin(dp[nxt][a][b][2], dp[cur][a][b][x] + get_cost(a, b, c, 2, c));
					}
				}
			}
		}
	}

	int ans = INF;
	for (int c = 0; c < 3; c++) {
		setmin(ans, dp[cur][locs[0].size()][locs[1].size()][c]);
	}
	if (ans == INF) ans = -1;
	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", S);
  ~~~~~^~~~~~~~~

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