Submission #107289

#	Time	Username	Problem	Language	Result	Execution time	Memory
107289		Diuven	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	401 ms	4344 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;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;


/*
앞에서부터, R, G, Y를 몇개씩 썼는지. 마지막이 뭔지
-> D[R][G][Y][c] = (distance with the nearest c) + _min(D[R-(c==0)][G-(c==1)][(c+1)/3], D[R-(c==0)][G-(c==1)][(c+2)/3]);
*/
int n, D[2][410][410][3];
int X[3][410];
char S[410];

inline int f(int x, int y){ return x<y ? y-x : 0; }
inline int _min(int x, int y){ return x<y ? x : y; }

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

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

	for(int i=1; i<=n; i++) X[0][i] = X[1][i] = X[2][i] = INF;

	for(int i=1; i<=n; i++){
		static int r, g, y;
		if(S[i]=='R') X[0][++r] = i;
		if(S[i]=='G') X[1][++g] = i;
		if(S[i]=='Y') X[2][++y] = 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 r=0; r<=n; r++, cout<<'\n')
	// 	for(int g=0; g<=n; g++, cout<<'\n')
	// 		for(int c=0; c<3; c++)
	// 			cout<<D[0][r][g][c]<<' ';
	// cout<<'\n';

	for(int i=1; i<=n; i++){
		int b = i&1;
		for(int r=0; r<=n; r++)
			for(int g=0; g<=n; g++)
				for(int c=0; c<3; c++)
					D[b][r][g][c] = INF;

		for(int r=0; r<=i; r++)
			for(int g=0; g+r<=i; g++){
				int Y[3] = {r,g,i-r-g};
				for(int c=0; c<3; c++){
					if(Y[c]<1){ D[b][r][g][c] = INF; continue; }
					int dist = f(i, X[c][Y[c]]);
					int p = (c+1)%3, q = (c+2)%3;
					int *E= D[!b][r-(c==0)][g-(c==1)];
					D[b][r][g][c] = dist + _min(E[p], E[q]);
				}
			}

		// for(int r=0; r<=n; r++, cout<<'\n')
		// 	for(int g=0; g<=n; g++, cout<<'\n')
		// 		for(int c=0; c<3; c++)
		// 			cout<<D[b][r][g][c]<<' ';
		// cout<<'\n';
	}

	/*

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

	for(int i=1; i<=n; i++){
		int b = i&1, c = !b;
		for(int r=0; r<=n; r++) for(int g=0; g<=n; g++) D[b][r][g] = INF;
		for(int r=0; r<=i; r++)
			for(int g=0; r+g<=i; g++){
				D[b][r+1][g] = _min(D[b][r+1][g], D[c][r][g]+f(i,X[0][r+1]));
				D[b][r][g+1] = _min(D[b][r][g+1], D[c][r][g]+f(i,X[1][g+1]));
				D[b][r][g] = _min(D[b][r][g], D[c][r][g]+f(i,X[2][i-r-g]));
			}
		cout<<'\n';
		for(int r=0; r<=n; r++, cout<<'\n') for(int g=0; g<=n; g++) cout<<D[b][r][g]<<' ';
	}
	*/

	int ans = INF;
	for(int r=0; r<=n; r++)
		for(int g=0; r+g<=n; 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: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25