Submission #1284448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284448		Jawad_Akbar_JJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	599 ms	780972 KiB

joi2019_ho_t3

#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=1;i<=n;i++){
		for (int j=0;j<=n;j++){
			if (s[i] == 'Y'){
				B[i][0][j] = min(B[i][0][j], R[i-1][j][0] + j);
				B[i][j][0] = min(B[i][j][0], G[i-1][j][0] + j);

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

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

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

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

				R[i][0][j+1] = min(R[i][0][j+1], G[i-1][0][j] + j + 1);
				R[i][j+1][0] = min(R[i][j+1][0], B[i-1][0][j] + j + 1);
			}
			for (int k=0;k<=n;k++){

				if (s[i] == 'Y'){
					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][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 (j > 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][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][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]));
	// cout<<R[n][0][0]<<" "<<G[n][0][0]<<" "<<B[n][0][0]<<endl;

	if (Mn == 1e9)
		Mn = -1;
	cout<<Mn<<'\n';
}

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