Submission #411770

#	Time	Username	Problem	Language	Result	Execution time	Memory
411770		nichke	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	228 ms	385772 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n;
string s;

const int INF = 1e9 + 9;

int cnt[3];
int pos[3][405];
int pref[3][405];

int a[405];
int dp[3][405][405][405];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') {
			a[i + 1] = 0; cnt[0]++;
			pos[0][cnt[0]] = i + 1;
		} else if (s[i] == 'G') {
			a[i + 1] = 1; cnt[1]++;
			pos[1][cnt[1]] = i + 1;
		} else {
			a[i + 1] = 2; cnt[2]++;
			pos[2][cnt[2]] = i + 1;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 1; j <= n; j++) {
			pref[i][j] = pref[i][j - 1];
			if (a[j] == i) pref[i][j]++;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int r = 0; r <= cnt[0]; r++) {
			for (int g = 0; g <= cnt[1]; g++) {
				for (int y = 0; y <= cnt[2]; y++) {
					dp[i][r][g][y] = INF;
				}
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[1][0][0][0] = 0;
	dp[2][0][0][0] = 0;
	for (int r = 0; r <= cnt[0]; r++) {
		for (int g = 0; g <= cnt[1]; g++) {
			for (int y = 0; y <= cnt[2]; y++) {
				for (int pre = 0; pre < 3; pre++) {
					for (int cur = 0; cur < 3; cur++) {
						if (cur == pre) continue;
						if ((cur == 0 && r == cnt[0])) continue;
						if ((cur == 1 && g == cnt[1])) continue;
						if ((cur == 2 && y == cnt[2])) continue;
						int ans = 0;
						int p1, p2, p3, dif;
						if (pre == 0) {
							p1 = pos[0][r];
							if (cur == 1) {
								p2 = pos[1][g + 1];
								p3 = pos[2][y];
								dif = 2;
							} else {
								p2 = pos[2][y + 1];
								p3 = pos[1][g];
								dif = 1;
							}
						} else if (pre == 1) {
							p1 = pos[1][g];
							if (cur == 0) {
								p2 = pos[0][r + 1];
								p3 = pos[2][y];
								dif = 2;
							} else {
								p2 = pos[2][y + 1];
								p3 = pos[0][r];
								dif = 0;
							}
						} else {
							p1 = pos[2][y];
							if (cur == 0) {
								p2 = pos[0][r + 1];
								p3 = pos[1][g];
								dif = 1;
							} else {
								p2 = pos[1][g + 1];
								p3 = pos[0][r];
								dif = 0;
							}
						}
						ans += max(0LL, pref[pre][p2] - pref[pre][p1]);
						ans += max(0LL, pref[dif][p2] - pref[dif][p3]);
						ans += dp[pre][r][g][y];
						if (cur == 0) {
							dp[cur][r + 1][g][y] = min(dp[cur][r + 1][g][y], ans);
						} else if (cur == 1) {
							dp[cur][r][g + 1][y] = min(dp[cur][r][g + 1][y], ans);
						} else {
							dp[cur][r][g][y + 1] = min(dp[cur][r][g][y + 1], ans);
						}
					}
				}
			}
		}
	}
	int ans = INF;
	for (int i = 0; i < 3; i++) {
		ans = min(ans, dp[i][cnt[0]][cnt[1]][cnt[2]]);
	}
	if (ans == INF) {
		cout << -1 << '\n';
	} else {
		cout << ans << '\n';
	}
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~

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