Submission #1284451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284451		Jawad_Akbar_JJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	614 ms	780480 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++){
				int vl = j + k + 1;
				
				if (s[i] == 'Y'){
					if (k > 0 and R[i-1][j][k] < R[i][j][k-1])
						R[i][j][k-1] = R[i-1][j][k];
					if (k > 0 and G[i-1][j][k] < G[i][j][k-1])
						G[i][j][k-1] = G[i-1][j][k];

					if (B[i-1][j][k] + j + k + 1 < B[i][j+1][k])
						B[i][j+1][k] = B[i-1][j][k] + vl;
					if (B[i-1][j][k] + j + k + 1 < B[i][j][k+1])
						B[i][j][k+1] = B[i-1][j][k] + vl;
				}

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

					if (G[i-1][j][k] + j + k + 1 < G[i][j+1][k])
						G[i][j+1][k] = G[i-1][j][k] + vl;
					if (G[i-1][j][k] + j + k + 1 < G[i][j][k+1])
						G[i][j][k+1] = G[i-1][j][k] + vl;
				}

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

					if (R[i-1][j][k] + j + k + 1 < R[i][j+1][k])
						R[i][j+1][k] = R[i-1][j][k] + vl;
					if (R[i-1][j][k] + j + k + 1 < R[i][j][k+1])
						R[i][j][k+1] = R[i-1][j][k] + vl;
				}
			}
		}
	}

	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