Submission #891831

#	Time	Username	Problem	Language	Result	Execution time	Memory
891831		Vvnx	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	73 ms	309072 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<ll> 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(i);
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(i);
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(i);
		}
	}
	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<=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]) + abs(i+j+k-pos[0][i-1]);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + abs(i+j+k-pos[1][j-1]);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + abs(i+j+k-pos[2][k-1]);
			}
		}
	}
	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/2 << endl;
}

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