Submission #892130

#	Time	Username	Problem	Language	Result	Execution time	Memory
892130		AMnu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	66 ms	338772 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;
vector<pii> pos[5];
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].pb(pii(g,b));
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(pii(r,b));
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(pii(r,g));
		}
	}
	if(r > (n+1)/2 || g > (n+1)/2 || b > (n+1)/2) {
		cout << -1 << endl;
		return 0;
	}
	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,pos[0][i-1].fi-j) + max(0,pos[0][i-1].se-k);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + max(0,pos[1][j-1].fi-i) + max(0,pos[1][j-1].se-k);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + max(0,pos[2][k-1].fi-i) + max(0,pos[2][k-1].se-j);
			}
		}
	}
	ll ans = min(dp[r][g][b][0],min(dp[r][g][b][1],dp[r][g][b][2]));
	cout << ans << endl;
}

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