Submission #1284440

#TimeUsernameProblemLanguageResultExecution timeMemory
1284440Jawad_Akbar_JJGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
417 ms780380 KiB
#include <iostream>

using namespace std;
const int N = 405;
int R[N][N][N], B[N][N][N], G[N][N][N];

signed main(){
	for (int i=0;i<N;i++){
		for (int j=0;j<N;j++)
			for (int k=(i + j == 0);k<N;k++)
				R[i][j][k] = G[i][j][k] = B[i][j][k] = 1e9;
	}

	int n;
	string s;
	cin>>n>>s;
	s = '0' + s;
	for (int i=0;i<=n;i++){
		if (s[i] == 'Y')
			s[i] = 'B';
	}

	for (int i=1;i<=n;i++){
		for (int j=n;j>=0;j--){
			for (int k=n;k>=0;k--){

				if (s[i] == 'B'){
					if (k > 0)
						R[i][j][k-1] = min(R[i][j][k-1], R[i-1][j][k]);
					if (k > 0)
						G[i][j][k-1] = min(G[i][j][k-1], G[i-1][j][k]);
					B[i][0][k] = min(B[i][0][k], R[i-1][k][0] + k);
					B[i][k][0] = min(B[i][k][0], G[i-1][k][0] + k);

					B[i][j+1][k] = min(B[i][j+1][k], B[i-1][j][k] + j + k + 1);
					B[i][j][k+1] = min(B[i][j][k+1], B[i-1][j][k] + j + k + 1);
				}

				if (s[i] == 'G'){
					if (k > 0)
						R[i][j-1][k] = min(R[i][j-1][k], R[i-1][j][k]);
					if (k > 0)
						B[i][j][k-1] = min(B[i][j][k-1], B[i-1][j][k]);

					G[i][0][k] = min(G[i][0][k], R[i-1][0][k] + k);
					G[i][k][0] = min(G[i][k][0], B[i-1][k][0] + k);

					G[i][j+1][k] = min(G[i][j+1][k], G[i-1][j][k] + j + k + 1);
					G[i][j][k+1] = min(G[i][j][k+1], G[i-1][j][k] + j + k + 1);
				}

				if (s[i] == 'R'){
					if (j > 0)
						B[i][j-1][k] = min(B[i][j-1][k], B[i-1][j][k]);
					if (j > 0)
						G[i][j-1][k] = min(G[i][j-1][k], G[i-1][j][k]);

					R[i][0][k] = min(R[i][0][k], G[i-1][0][k] + k);
					R[i][k][0] = min(R[i][k][0], B[i-1][0][k] + k);

					R[i][j+1][k] = min(R[i][j+1][k], R[i-1][j][k] + j + k + 1);
					R[i][j][k+1] = min(R[i][j][k+1], R[i-1][j][k] + j + k + 1);
				}
			}
		}
	}

	int Mn = min(R[n][0][0], min(G[n][0][0], B[n][0][0]));
	if (Mn == 1e9)
		Mn = -1;
	cout<<Mn<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...