Submission #1104919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104919		Champ_Naman	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	109 ms	430920 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'

int dp[401][401][401][3];

inline void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	s = " "+s;

	int pre[3][n+1], p[3][n+1], c[3];
	for(int l=0; l<3; l++) c[l] = 0, pre[l][0] = 0;

	for(int i=1; i<=n; i++){
		if(s[i] == 'R') p[0][++c[0]] = i;
		else if(s[i] == 'G') p[1][++c[1]] = i;
		else p[2][++c[2]] = i;

		for(int l=0; l<3; l++) pre[l][i] = c[l];
	}

	for(int l=0; l<3; l++) dp[0][0][0][l] = 0;

	for(int i=1; i<=n; i++){
		for(int r=0; r<=min(c[0], i); r++){
			for(int g=0; g<=min(c[1], i-r); g++){
				int y = i - r - g;
				if(y > c[2]) continue;

				if(r > 0) dp[i][r][g][0] = min(dp[i-1][r-1][g][1], dp[i-1][r-1][g][2]) + max(0, g - pre[1][p[0][r]]) + max(0, y - pre[2][p[0][r]]);
				else dp[i][r][g][0] = 1e9;

				if(g > 0) dp[i][r][g][1] = min(dp[i-1][r][g-1][0], dp[i-1][r][g-1][2]) + max(0, r - pre[0][p[1][g]]) + max(0, y - pre[2][p[1][g]]);
				else dp[i][r][g][1] = 1e9;

				if(y > 0) dp[i][r][g][2] = min(dp[i-1][r][g][0], dp[i-1][r][g][1]) + max(0, g - pre[1][p[2][y]]) + max(0, r - pre[0][p[2][y]]);
				else dp[i][r][g][2] = 1e9;
			}
		}
	}

	int ans = min({dp[n][c[0]][c[1]][0], dp[n][c[0]][c[1]][1], dp[n][c[0]][c[1]][2]});
	cout<<(ans >= 1e9 ? -1 : ans)<<nl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	//cin>>t;
	while(t--) solve();

	return 0;
}

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