제출 #1284445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284445		Jawad_Akbar_JJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	732 ms	780420 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++){
			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][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);
					B[i][0][k+1] = min(B[i][0][k+1], R[i-1][k][0] + k + 1);
					B[i][k+1][0] = min(B[i][k+1][0], G[i-1][k][0] + 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][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);
					G[i][0][k+1] = min(G[i][0][k+1], R[i-1][0][k] + k + 1);
					G[i][k+1][0] = min(G[i][k+1][0], B[i-1][k][0] + 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);
					R[i][0][k+1] = min(R[i][0][k+1], G[i-1][0][k] + k + 1);
					R[i][k+1][0] = min(R[i][k+1][0], B[i-1][0][k] + 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