Submission #107382

#	Time	Username	Problem	Language	Result	Execution time	Memory
107382		Diuven	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	261 ms	3644 KiB

joi2019_ho_t3

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

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 1<<20;

int n;
char ST[410];

int P[3][410], S[3][410], F[3];
int D[2][410][410][3];

inline int _min(int x, int y){ return x<y ? x : y; }
inline int _max(int x, int y){ return x>y ? x : y; }

int dist(int r, int g, int y, int x){
	int res = 0, C[3] = {r,g,y};
	for(int k=0; k<3; k++)
		res += _max(0, S[k][x]-C[k]);
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>(ST+1);

	{
		int T[128]={};
		T['R'] = 0, T['G'] = 1, T['Y'] = 2;

		for(int i=1; i<=n+1; i++) for(int k=0; k<3; k++)
			P[k][i] = INF;

		for(int i=1; i<=n; i++){
			int x = T[int(ST[i])];

			P[x][++F[x]] = i;
			for(int k=0; k<3; k++) S[k][i] = S[k][i-1];
			S[x][i]++;
		}
	}

	for(int r=0; r<=n; r++) for(int g=0; g<=n; g++)
		for(int c=0; c<3; c++) D[0][r][g][c] = INF;
	D[0][0][0][0] = D[0][0][0][1] = D[0][0][0][2] = 0;

	for(int i=1; i<=n; i++){
		int z = i&1;
		
		for(int r=0; r<=F[0]; r++) for(int g=0; g<=F[1]; g++){
			int U[3] = {r, g, i-r-g};
			for(int c=0; c<3; c++){
				if(U[c]<1 || U[2]>F[2]){ D[z][r][g][c] = INF; continue; }
				U[c]--;
				int cost = dist(U[0],U[1],U[2],P[c][U[c]+1]-1);
				int get = _min(D[!z][U[0]][U[1]][(c+1)%3], D[!z][U[0]][U[1]][(c+2)%3]);
				D[z][r][g][c] = _min(INF, cost + get);
				U[c]++;
			}
		}
		// for(int r=0; r<=F[0]; r++, cout<<'\n') for(int g=0; g<=F[1]; g++, cout<<'\n'){
		// 	for(int c=0; c<3; c++) cout<<D[z][r][g][c]<<' ';
		// }
		// cout<<'\n';
	}

	int ans = INF;


	for(int r=0; r<=F[0]; r++)	for(int g=0; g<=F[1]; g++)
		for(int c=0; c<3; c++) ans = _min(ans, D[n&1][r][g][c]);
	
	if(ans>=INF) ans = -1;
	cout<<ans<<'\n';

	return 0;
}

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