Submission #707060

#	Time	Username	Problem	Language	Result	Execution time	Memory
707060		blacktulip	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	479 ms	1002468 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo; 
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 400;
const lo mod = 1000000007;
 
int n,m,k,flag,t,x,siz1,siz2,siz3,dp[li][li][li][4],ind1[3][li],ind2[3][li],ind[3][li];
int cev;
string s;
vector<int> v[3];
 
inline int in(){
    int x;
    scanf("%d",&x);
    return x;
}

inline int f(int bir,int iki,int uc,int sira,int son){
	int cevv=1000000000;
	if(bir==siz1 && iki==siz2 && uc==siz3)return 0;
	if(~dp[bir][iki][uc][son])return dp[bir][iki][uc][son];
	if(bir!=siz1){
		if(son!=0)cevv=min(cevv,f(bir+1,iki,uc,sira+1,0)+max(0,(v[0][bir]+max(0,iki-ind[1][bir]-1)+max(0,uc-ind[2][bir]-1))-sira));
	}
	if(iki!=siz2){
		if(son!=1)cevv=min(cevv,f(bir,iki+1,uc,sira+1,1)+max(0,(v[1][iki]+max(0,bir-ind1[0][iki]-1)+max(0,uc-ind1[2][iki]-1))-sira));
	}
	if(uc!=siz3){
		if(son!=2)cevv=min(cevv,f(bir,iki,uc+1,sira+1,2)+max(0,(v[2][uc]+max(0,iki-ind2[1][uc]-1)+max(0,bir-ind2[0][uc]-1))-sira));
	}
	return dp[bir][iki][uc][son]=cevv;
}

int main(void){
    fio();
    cin>>n;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
		if(s[i]=='R'){s[i]='a';siz1++;}
		if(s[i]=='G'){s[i]='b';siz2++;}
		if(s[i]=='Y'){s[i]='c';siz3++;}
		v[s[i]-'a'].pb(i);
	}
	for(int i=0;i<(int)v[0].size();i++){
		ind[1][i]=-1;
		ind[2][i]=-1;
		for(int j=0;j<(int)v[1].size();j++){
			if(v[1][j]>v[0][i]){break;}
			ind[1][i]=j;
		}
		for(int j=0;j<(int)v[2].size();j++){
			if(v[2][j]>v[0][i]){break;}
			ind[2][i]=j;
		}
		
	}
	for(int i=0;i<(int)v[1].size();i++){
		ind1[0][i]=-1;
		ind1[2][i]=-1;
		for(int j=0;j<(int)v[0].size();j++){
			if(v[0][j]>v[1][i]){break;}
			ind1[0][i]=j;
		}
		for(int j=0;j<(int)v[2].size();j++){
			if(v[2][j]>v[1][i]){break;}
			ind1[2][i]=j;
		}
		
	}
	for(int i=0;i<(int)v[2].size();i++){
		ind2[0][i]=-1;
		ind2[1][i]=-1;
		for(int j=0;j<(int)v[0].size();j++){
			if(v[0][j]>v[2][i]){break;}
			ind2[0][i]=j;
		}
		for(int j=0;j<(int)v[1].size();j++){
			if(v[1][j]>v[2][i]){break;}
			ind2[1][i]=j;
		}
		//~ cout<<i<<" :: "<<ind2[0][i]<<" :: "<<ind2[1][i]<<endl;
	}
	int yaz=f(0,0,0,0,3);
	if(yaz>=1000000000)yaz=-1;
	cout<<yaz;
    return 0;
}

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