oj.uz

Submission #114829

# Submission time Handle Problem Language Result Execution time Memory
114829 2019-06-03T11:21:32 Z dsjong Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 914584 KB 
#include<bits/stdc++.h>
using namespace std;
int N,tr,tg,ty;
string s;
vector<int>cnt[4];
int dp[405][405][405][4];
int lol[405][4];
int go(int r,int g,int y,int l){
	if(dp[r][g][y][l]!=-1) return dp[r][g][y][l];
	int &ans=dp[r][g][y][l];
	int n=r+g+y;
	if(n==0) return 0;
	ans=1e9;
	int extras=0;
	if(l==1&&r>0){
		int lb1=min(g,lol[cnt[1][r-1]][2]);
		int lb2=min(y,lol[cnt[1][r-1]][3]);
		extras=g+y-lb1-lb2;
		int add=extras+cnt[1][r-1]-n+1;
		ans=min(ans,go(r-1,g,y,2)+add);
		ans=min(ans,go(r-1,g,y,3)+add);
	}
	else if(l==2&&g>0){
		int lb1=min(r,lol[cnt[2][g-1]][1]);
		int lb2=min(y,lol[cnt[2][g-1]][3]);
		extras=r+y-lb1-lb2;
		int add=extras+cnt[2][g-1]-n+1;
		ans=min(ans,go(r,g-1,y,1)+add);
		ans=min(ans,go(r,g-1,y,3)+add);
	}
	else if(l==3&&y>0){
		int lb1=min(r,lol[cnt[3][y-1]][1]);
		int lb2=min(g,lol[cnt[3][y-1]][2]);
		extras=g+r-lb1-lb2;
		int add=extras+cnt[3][y-1]-n+1;
		ans=min(ans,go(r,g,y-1,1)+add);
		ans=min(ans,go(r,g,y-1,2)+add);
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>N>>s;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<N;i++){
		if(s[i]=='R'){
			tr++;
			cnt[1].push_back(i);
		}
		else if(s[i]=='G'){
			tg++;
			cnt[2].push_back(i);
		}
		else{
			ty++;
			cnt[3].push_back(i);
		}
	}
	for(int t=1;t<=3;t++){
		int last=0;
		for(int i=0;i<cnt[t].size();i++){
			for(int j=last;j<=cnt[t][i];j++){
				lol[j][t]=i;
			}
			last=cnt[t][i]+1;
		}
		for(int j=last;j<=402;j++){
			lol[j][t]=cnt[t].size();
		}
	}
	int ans=min({go(tr,tg,ty,1),go(tr,tg,ty,2),go(tr,tg,ty,3)});
	if(ans==1e9||ans==-1) cout<<-1;
	else cout<<ans;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cnt[t].size();i++){
               ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 868920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 868920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1133 ms 914584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 868920 KB Time limit exceeded
2 Halted 0 ms 0 KB -