Submission #507588

#	Time	Username	Problem	Language	Result	Execution time	Memory
507588		CSQ31	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	272 ms	384776 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int dp[3][401][401][401],pos[3][401],cnt[3];
int cost[3][3][401][401];
void chmin(int &x,int y){
	x = min(x,y);
}
int main()
{
	int n;
	string s;
	cin>>n>>s;
	vector<int>c;
	for(char x:s){
		if(x == 'R')c.push_back(0);
		if(x == 'G')c.push_back(1);
		if(x == 'Y')c.push_back(2);
	}
	for(int i=0;i<=n;i++)pos[0][i] = pos[1][i] = pos[2][i] = -1;
	for(int i=0;i<n;i++)pos[c[i]][cnt[c[i]]++] = i;
	/*
	for(int i=0;i<3;i++){
		for(int j=0;j<cnt[i];j++)cout<<pos[i][j]<<" ";
		cout<<'\n';
	}*/
	for(int c1=0;c1<3;c1++){
		for(int c2=0;c2<3;c2++){
			if(c1 == c2)continue;
			for(int i=0;i<cnt[c1];i++){
				for(int j=0;j<cnt[c2];j++){
					cost[c1][c2][i][j] = pos[c2][j] > pos[c1][i];
					if(j)cost[c1][c2][i][j]+=cost[c1][c2][i][j-1];	
				}	
			}
		}
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=0;k+j<=i;k++)
				dp[0][i][j][k] = dp[1][i][j][k] = dp[2][i][j][k] = INF;
				
				
	
	dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
	array<int,3>p;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k+j<=i;k++){
				p = {j,k,i-j-k}; //number of rgy
				
				for(int c1=0;c1<3;c1++){ //previous color
					if(dp[c1][i][j][k] == INF)continue; 
					for(int c2=0;c2<3;c2++){ //current color
						if(c1 == c2 || pos[c2][p[c2]] == -1)continue;
						int tot = 0;
						for(int c3=0;c3<3;c3++){
							if(p[c3])tot+=cost[c2][c3][p[c2]][p[c3]-1];
						}
						if(c2 == 0)chmin(dp[0][i+1][j+1][k],dp[c1][i][j][k] + tot);
						if(c2 == 1)chmin(dp[1][i+1][j][k+1],dp[c1][i][j][k] + tot);
						if(c2 == 2)chmin(dp[2][i+1][j][k],dp[c1][i][j][k] + tot);
					}
					
				}
			}
		}
	}
	int mn = INF;
	for(int i=0;i<3;i++)mn = min(mn,dp[i][n][cnt[0]][cnt[1]]);
	if(mn == INF)mn = -1;
	cout<<mn<<'\n';
	
	
}

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