oj.uz

Submission #533626

# Submission time Handle Problem Language Result Execution time Memory
533626 2022-03-06T16:54:49 Z alvingogo Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 6092 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

const int inf=1e8;
int dp[405][405][3][3];
int getdp(int x,int y,int p,int q){
	if(x>y){
		return 0;
	}
	return dp[x][y][p][q];
}
int main(){
	AquA;
	for(int i=0;i<405;i++){
		for(int j=0;j<405;j++){
			for(int p=0;p<3;p++){
				for(int q=0;q<3;q++){
					dp[i][j][p][q]=inf;
				}
			}
		}
	}
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		if(s[i]=='R'){
			v[i]=0;
		}
		else if(s[i]=='G'){
			v[i]=1;
		}
		else{
			v[i]=2;
		}
	}
	for(int t=1;t<=n;t++){
		for(int l=0;l+t-1<n;l++){
			int r=l+t-1;
			if(t==1){
				dp[l][r][v[l]][v[r]]=0;
			}
			else{
				for(int p=0;p<3;p++){
					for(int q=0;q<3;q++){
						if(v[l]==p){
							for(int a=0;a<3;a++){
								if(a!=v[l]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l+1,r,a,q));
								}
							}
						}
						int y=0;
						for(int m=l+1;m<r;m++){
							if(v[m]!=v[l]){
								y++;
							}
							for(int u=0;u<3;u++){
								if(u!=v[l]){
									for(int z=0;z<3;z++){
										if(z!=v[l]){
											dp[l][r][p][q]=min(dp[l][r][p][q],y+getdp(l+1,m,p,u)+getdp(m+1,r,z,q));
										}
									}
								}
							}
						}
						if(v[r]!=v[l]){
							y++;
						}
						if(v[l]==q){
							for(int a=0;a<3;a++){
								if(a!=v[l]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l+1,r,p,a)+y);
								}
							}
						}
						if(v[r]==q){
							for(int a=0;a<3;a++){
								if(a!=v[r]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l,r-1,p,a));
								}
							}
						}
						int y2=0;
						for(int m=r-1;m>l;m--){
							if(v[m]!=v[r]){
								y2++;
							}
							for(int u=0;u<3;u++){
								if(u!=v[r]){
									for(int z=0;z<3;z++){
										if(z!=v[r]){
											dp[l][r][p][q]=min(dp[l][r][p][q],y2+getdp(l,m-1,p,u)+getdp(m,r-1,z,q));
										}
									}
								}
							}
						}
						if(v[l]!=v[r]){
							y2++;
						}
						if(v[r]==p){
							for(int a=0;a<3;a++){
								if(a!=v[r]){
									dp[l][r][p][q]=min(dp[l][r][p][q],getdp(l,r-1,a,q)+y2);
								}
							}
						}
					}
				}
			}
		}
	}
	/*
	for(int i=0;i<n;i++){
		for(int j=i;j<=n;j++){
			for(int p=0;p<3;p++){
				for(int q=0;q<3;q++){
					if(dp[i][j][p][q]!=inf){
						cout << i << " " << j << " " << p << " " << q << " " << dp[i][j][p][q] << "\n";
					}
				}
			}
		}
	}
	*/
	int ans=inf;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			ans=min(ans,dp[0][n-1][i][j]);
		}
	}
	if(ans==inf){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 3 ms 6040 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 3 ms 6092 KB Output is correct
6 Correct 3 ms 6088 KB Output is correct
7 Correct 3 ms 6088 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 6092 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct
11 Correct 3 ms 6092 KB Output is correct
12 Incorrect 3 ms 6092 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 3 ms 6040 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 3 ms 6092 KB Output is correct
6 Correct 3 ms 6088 KB Output is correct
7 Correct 3 ms 6088 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 6092 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct
11 Correct 3 ms 6092 KB Output is correct
12 Incorrect 3 ms 6092 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6092 KB Output is correct
2 Execution timed out 1090 ms 6092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 3 ms 6040 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 3 ms 6092 KB Output is correct
6 Correct 3 ms 6088 KB Output is correct
7 Correct 3 ms 6088 KB Output is correct
8 Correct 3 ms 5964 KB Output is correct
9 Correct 3 ms 6092 KB Output is correct
10 Correct 3 ms 5964 KB Output is correct
11 Correct 3 ms 6092 KB Output is correct
12 Incorrect 3 ms 6092 KB Output isn't correct
13 Halted 0 ms 0 KB -