Submission #1317793

#TimeUsernameProblemLanguageResultExecution timeMemory
1317793JuanJLGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
1110 ms320560 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

string opc = "RGY";
const int MAXN = 400+1;

int dp[401][5][202][202];

ll n;
string s;
vector<vector<ll>> pos(3);
map<char,ll> ri;

ll select(ll k , ll R, ll G){
	if(k==0) return R;
	if(k==1) return G;
}

int f(ll x, ll ant, ll R, ll G){
	
	int &res = dp[x][ant][R][G];
	if(res!=-1) return res;
	if(x==n) return 0;

	res = 10000000;
	forn(k,0,2){
		if(k==ant) continue;
		
		ll rgy = select(k,R,G);
		if(rgy==SZ(pos[k])) continue;

		
		int cost = 0;
		ll j = pos[k][rgy];
		forn(h,0,3){
			ll mrgy = select(h,R,G);
			cost += max((ll)0,(lower_bound(ALL(pos[h]),j)-pos[h].begin()) - mrgy);
		}

		ll nR = R; if(k==0) nR++;
		ll nG = G; if(k==1) nG++;
		
		res=min(res, f(x+1,k,nR,nG)+cost);
	}
	//cout<<x<<" "<<R<<" "<<G<<" "<<Y<<"-------> "<<res<<'\n';
	return res;
}
int main(){ FIN;
	cin>>n;
	cin>>s;

	ri['R']=0;
	ri['G']=1;

	forn(i,0,n) pos[ri[s[i]]].pb(i);

	if(SZ(pos[0])>=202 || SZ(pos[1])>=202 || abs(SZ(pos[0])-SZ(pos[1]))>=2){
		cout<<-1<<'\n';
		exit(0);
	}

	mset(dp,-1);

	ll res=f(0,4,0,0);

	if(res>1000000000) cout<<"-1"<<'\n';
	else cout<<res<<'\n';
	
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'll select(ll, ll, ll)':
joi2019_ho_t3.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...