Submission #892362

#	Time	Username	Problem	Language	Result	Execution time	Memory
892362		Vvnx	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	59 ms	250388 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[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].pb({g,b});
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb({r,b});
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb({r,g});
		}
	}
	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<=2; 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],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