Submission #1319297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319297		vtnoo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	275 ms	135296 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<ll, ll>
using namespace std;
const int nax=205,inf=1e9;
int n,dp[4][nax][nax][nax]; //ultimo color usado, cuantos rojos/verdes/amarillos
//~ int pf[3][nax];
void chmin(int &a,int b){
	a=min(a,b);
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	cin>>n;
	string s;cin>>s;
	vector<vi>pos(3);
	L(i,0,n-1){
		if(s[i]=='R'){
			pos[0].pb(i);
		}else if(s[i]=='G'){
			pos[1].pb(i);
		}else{
			pos[2].pb(i);    
		}
	}
	//~ L(i,1,nax-1)pf[0][i]+=pf[0][i-1],pf[1][i]+=pf[1][i-1],pf[2][i]+=pf[2][i-1];
	L(i,0,3)L(j,0,nax-1)L(k,0,nax-1)L(l,0,nax-1)dp[i][j][k][l]=inf;
	dp[3][0][0][0]=0;
	L(a,0,sz(pos[0])){
		L(b,0,sz(pos[1])){
			L(c,0,sz(pos[2])){
				if(a>=nax||b>=nax||c>=nax){
					cout<<-1<<endl;
					return 0;
				}
				int tot=a+b+c;
				L(lst,0,3){
					if(dp[lst][a][b][c]==inf)continue;
					L(act,0,2){
						if(lst!=3&&lst==act)continue;
						if(act==0&&a==sz(pos[0]))continue;
						if(act==1&&b==sz(pos[1]))continue;
						if(act==2&&c==sz(pos[2]))continue;
						int used=(act==0?a:(act==1?b:c)),piv=pos[act][used];
						int cntR=lower_bound(all(pos[0]),piv)-pos[0].begin();
						int cntG=lower_bound(all(pos[1]),piv)-pos[1].begin();
						int cntY=lower_bound(all(pos[2]),piv)-pos[2].begin();
						int smaller=min(cntR,a)+min(cntG,b)+min(cntY,c);
						int greater=tot-smaller;
						int na=a+(act==0),nb=b+(act==1),nc=c+(act==2);
						auto &res=dp[act][na][nb][nc];
						chmin(res,dp[lst][a][b][c]+greater);
					}
				}
			}
		}
	}
	int ans=inf;
	L(i,0,2)ans=min(ans,dp[i][sz(pos[0])][sz(pos[1])][sz(pos[2])]);
	if(ans==inf)cout<<-1<<endl;
	else cout<<ans<<endl;
}	

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