Submission #98031

#	Time	Username	Problem	Language	Result	Execution time	Memory
98031		giorgikob	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	138 ms	163196 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
using namespace std;

const int N = 5e5+5;

ll n, m, k, x, y, a, b, t, q, ans, sum;

vector< ll > g_ind, r_ind, y_ind;

ll A[N],B[N];
char C[N];

int G,R,Y;
int g_num[N], r_num[N], y_num[N];
int ind;

int dp[405][405][405][4];

int calc(int x,int y){
	
	if(x==-1 && y==-1)return -1;
	if(x==-1)return y;
	if(y==-1)return x;
	
	return min(x,y);
}

int main()
{
	ios::sync_with_stdio(0);
	
	g_ind.push_back(0);
	r_ind.push_back(0);
	y_ind.push_back(0);
	
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> C[i];
		
		g_num[i] = g_num[i-1];
		r_num[i] = r_num[i-1];
		y_num[i] = y_num[i-1];
		
		if( C[i] == 'G' ){
			g_ind.push_back(i);
			G++;
			g_num[i]++;
		}
		
		if( C[i] == 'R' ){
			r_ind.push_back(i);
			R++;
			r_num[i]++;
		}
		
		if( C[i] == 'Y' ){
			y_ind.push_back(i);
			Y++;
			y_num[i]++;
		}
	}
	
	for(int g = 0; g <= G; g++ )
		for(int r = 0; r <= R; r++ )
			for(int y = 0; y <= Y; y++ )
			for(int i=1;i<=3;i++)
			dp[g][r][y][i]=-1;
	
	for(int i=1;i<=3;i++)
	dp[0][0][0][i]=0;
	
	for(int g = 0; g <= G; g++ )
		for(int r = 0; r <= R; r++ )
			for(int y = 0; y <= Y; y++ ){
				
				int sul = g+r+y;
				sul++;
				sul /= 2;
				
				ind = g_ind[g];
				
				if(  g>0 && g<=sul ){
					int z = calc( dp[g - 1][r][y][2] , dp[g - 1][r][y][3] );
					if(z!=-1)
					dp[g][r][y][1] = z + max(0,(r_num[ind] - r_num[r_ind[r]])) + max(0,(y_num[ind] - y_num[y_ind[y]]));  	
				}
				
				ind = r_ind[r];
				
				if( r>0 && r<=sul ){
					int z = calc( dp[g][r - 1][y][1] , dp[g][r - 1][y][3] );
					if(z!=-1)
					dp[g][r][y][2] = z + max(0,(g_num[ind] - g_num[g_ind[g]])) + max(0,(y_num[ind] - y_num[y_ind[y]]));  	
				}
				
				ind = y_ind[y];
				
				if( y>0 && y<=sul ){
					int z = calc( dp[g][r][y - 1][1] , dp[g][r][y - 1][2] );
					if(z!=-1)
					dp[g][r][y][3] = z + max(0,(g_num[ind] - g_num[g_ind[g]])) + max(0,(r_num[ind] - r_num[r_ind[r]]));  	
				}
				
			//	cout << dp[g][r][y][1] <<" "<< dp[g][r][y][2] <<" "<< dp[g][r][y][3] << endl;
			//	cout<<g<<" "<<r<<" "<<y<<endl;
			//	cout<<endl;
			}
			
			
	cout << calc( dp[G][R][Y][1] , calc( dp[G][R][Y][2] , dp[G][R][Y][3] ) ) << endl;
}

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