Submission #892124

#	Time	Username	Problem	Language	Result	Execution time	Memory
892124		AMnu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	73 ms	330392 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second
 
const ll N = 403;
const ll INF = 1e9;
 
ll n,r,g,b;
string s;
int cnt[N][3];
vector <int> pos[3];
ll dp[N][N][N][3];
 
int main() {
	cin >> n >> s;
	s = '!' + s;
	for(int i=1; i<=n; i++) {
		if(s[i] == 'R') {
			r++;
			pos[0].push_back(i);
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].push_back(i);
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].push_back(i);
		}
		cnt[i][0] = r;
		cnt[i][1] = g;
		cnt[i][2] = b;
	}
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				for(int l=0; l<3; l++) dp[i][j][k][l] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1],dp[i-1][j][k][2]) + max(0,cnt[pos[0][i-1]][1]-j) + max(0,cnt[pos[0][i-1]][2]-k);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + max(0,cnt[pos[1][j-1]][0]-i) + max(0,cnt[pos[1][j-1]][2]-k);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + max(0,cnt[pos[2][k-1]][0]-i) + max(0,cnt[pos[2][k-1]][1]-j);
			}
		}
	}
	ll ans = min(dp[r][g][b][0],min(dp[r][g][b][1],dp[r][g][b][2]));
	if(ans >= INF) cout << -1 << endl;
	else cout << ans << endl;
}

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