Submission #1284454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284454		Jawad_Akbar_JJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	341 ms	4248 KiB

joi2019_ho_t3

#include <iostream>

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

signed main(){
	int n;
	string s;
	cin>>n>>s;
	s = '0' + s;

	for (int i : {0, 1}){
		for (int j=0;j<=n;j++)
			for (int k=0;k<=n;k++)
				if (i + j + k > 0)
					R[i][j][k] = G[i][j][k] = B[i][j][k] = 1e9;
	}

	for (int i=1;i<=n;i++){
		for (int j=0;j<=n;j++){
			if (s[i] == 'Y'){
				B[1][0][j] = min(B[1][0][j], R[0][j][0] + j);
				B[1][j][0] = min(B[1][j][0], G[0][j][0] + j);

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

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

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

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

				R[1][0][j+1] = min(R[1][0][j+1], G[0][0][j] + j + 1);
				R[1][j+1][0] = min(R[1][j+1][0], B[0][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[0][j][k] < R[1][j][k-1])
						R[1][j][k-1] = R[0][j][k];
					if (k > 0 and G[0][j][k] < G[1][j][k-1])
						G[1][j][k-1] = G[0][j][k];

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

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

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

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

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

		for (int j=0;j<=n;j++){
			for (int k=0;k<=n;k++){
				R[0][j][k] = R[1][j][k];
				G[0][j][k] = G[1][j][k];
				B[0][j][k] = B[1][j][k];

				G[1][j][k] = R[1][j][k] = B[1][j][k] = 1e9;
			}
		}
	}

	int Mn = min(R[0][0][0], min(G[0][0][0], B[0][0][0]));

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

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