제출 #265185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265185		Goolakh	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	551 ms	1048580 KiB

joi2019_ho_t3

// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=4e2+10, maxm=1e6+10, lg=17, mod=1e9+7, inf=1e18;

ll n,tt[3],tp[maxn][3],we[maxn][3], dp[maxn][maxn][maxn][3];
string s;
ll mem(ll c[3],ll b){
	ll &x=dp[c[0]][c[1]][c[2]][b];
	if(c[0]+c[1]+c[2]==0) return 0;
	if(x!=-1) return x;
	x=inf;
	ll tah=0; for(int g:{0,1,2}) tah=max(tah,we[c[g]][g]);
	for(int g:{0,1,2})if(c[g] && b!=g){
		c[g]--;
		ll xx=mem(c,g);
		c[g]++;
		for(int gg:{0,1,2})if(gg!=g) xx+=tp[tah][gg]-tp[we[c[g]][g]][gg];
		x=min(x,xx);
	}
	return x;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
		
	memset(dp,-1,sizeof(dp));
	cin>>n>>s;
	for(int i=0;i<n;i++){
		for(int j:{0,1,2}) tp[i][j]=tp[i-1][j];
		if(s[i]=='R') tp[i][0]++, we[++tt[0]][0]=i;
		if(s[i]=='G') tp[i][1]++, we[++tt[1]][1]=i;
		if(s[i]=='Y') tp[i][2]++, we[++tt[2]][2]=i;
	}
	ll ans=min({mem(tt,0),mem(tt,1),mem(tt,2)});
	cout<<(ans>=inf ? -1:ans);
	
	return 0;
}
// a denial a denial a denial a denial a denial a denial

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