Submission #781635

#	Time	Username	Problem	Language	Result	Execution time	Memory
781635		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	383 ms	758908 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#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 = 1000000000;
const lo li = 401;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,sr,sg,sy,arr[3][2][li][li],dp[li][li][li][3];
int cev;
string s;
vector<int> v[3];

inline int in(){
	int x;
	scanf("%d",&x);
	return x;
}

inline int add(int x,int y,int q,int z){
	if(z<0)return 0;
	return arr[x][y][q][z];
}

int f(int r,int g,int y,int son,int sira){
	int cevv=100000000;
	if(sira==n)return 0;
	if(~dp[r][g][y][son])return dp[r][g][y][son];
	if((r==0 && g==0 && y==0 && sr) || (son!=0 && r<sr)){
		cevv=min(cevv,f(r+1,g,y,0,sira+1)+v[0][r]+add(0,0,r,g-1)+add(0,1,r,y-1)-sira);
	}
	if(son!=1 && g<sg){
		cevv=min(cevv,f(r,g+1,y,1,sira+1)+v[1][g]+add(1,0,g,r-1)+add(1,1,g,y-1)-sira);
	}
	if(son!=2 && y<sy){
		cevv=min(cevv,f(r,g,y+1,2,sira+1)+v[2][y]+add(2,0,y,r-1)+add(2,1,y,g-1)-sira);
	}
	return dp[r][g][y][son]=cevv;
}

int main(void){
	fio();
	cin>>n>>s;
	memset(dp,-1,sizeof(dp));
	//R->G->Y
	for(int i=0;i<n;i++){
		if(s[i]=='R'){
			v[0].pb(i);
			sr++;
		}
		if(s[i]=='G'){
			v[1].pb(i);
			sg++;
		}
		if(s[i]=='Y'){
			v[2].pb(i);
			sy++;
		}
	}
	for(int i=0;i<sr;i++){
		int say=0;
		for(int j=0;j<sg;j++){
			if(v[0][i]<v[1][j])say++;
			arr[0][0][i][j]=say;
		}
		say=0;
		for(int j=0;j<sy;j++){
			if(v[0][i]<v[2][j])say++;
			arr[0][1][i][j]=say;
		}
	}
	for(int i=0;i<sg;i++){
		int say=0;
		for(int j=0;j<sr;j++){
			if(v[1][i]<v[0][j])say++;
			arr[1][0][i][j]=say;
		}
		say=0;
		for(int j=0;j<sy;j++){
			if(v[1][i]<v[2][j])say++;
			arr[1][1][i][j]=say;
		}
	}
	for(int i=0;i<sy;i++){
		int say=0;
		for(int j=0;j<sr;j++){
			if(v[2][i]<v[0][j])say++;
			arr[2][0][i][j]=say;
		}
		say=0;
		for(int j=0;j<sg;j++){
			if(v[2][i]<v[1][j])say++;
			arr[2][1][i][j]=say;
		}
	}
	cev=f(0,0,0,0,0);
	if(cev==100000000)cev=-1;
	cout<<cev<<endl;
	return 0;
}

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