Submission #936660

#	Time	Username	Problem	Language	Result	Execution time	Memory
936660		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	65 ms	249940 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define inf ((int)1e9)
using namespace std;
const int N = 403;
int dp[N][N][N][3];

int32_t main(){
	fast
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt[3] = {0, 0, 0};
	vector <vector<int> > pos(3);
	for(int i = 0; i < n; i++) {
		if(s[i] == 'R') {
			cnt[0]++;
			pos[0].push_back(i);
		}
		else if(s[i] == 'G') {
			cnt[1]++;
			pos[1].push_back(i);
		}
		else {
			cnt[2]++;
			pos[2].push_back(i);
		}
	}
	pos[0].push_back(inf);
	pos[1].push_back(inf);
	pos[2].push_back(inf);
	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 last = 0; last < 3; last++)
					dp[r][g][y][last] = inf;

	dp[1][0][0][0] = pos[0][0];
	dp[0][1][0][1] = pos[1][0];
	dp[0][0][1][2] = pos[2][0];
	for(int r = 0; r <= cnt[0]; r++) {
		int ir = pos[0][r];
		for(int g = 0; g <= cnt[1]; g++) {
			int ig = pos[1][g];
			for(int y = 0; y <= cnt[2]; y++) {
				int iy = pos[2][y];
				int ind = r + g + y;
				for(int last : {0, 1, 2}) {
					int val = dp[r][g][y][last];
					if(val >= inf) continue;
					//cout << r << " " << g << " " << y << "\n";
					//cout << ir << " " << ig << " " << iy << " " << ind << "\n";
					//cout << val << "\n";
					if(last != 0) {
						dp[r+1][g][y][0] = min(dp[r+1][g][y][0], val + abs(ir - ind));
					}
					if(last != 1) {
						dp[r][g+1][y][1] = min(dp[r][g+1][y][1], val + abs(ig - ind));
					}
					if(last != 2) {
						dp[r][g][y+1][2] = min(dp[r][g][y+1][2], val + abs(iy - ind));
					}
				}
			}
		}
	}
	int ans = inf;
	for(int i = 0; i < 3; i++) {
		ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
	}
	if(ans == inf) cout << -1;
	else cout << ans / 2;
}

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