Submission #494742

#	Time	Username	Problem	Language	Result	Execution time	Memory
494742		Haruto810198	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	75 ms	59224 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 410;

int n;
char arr[MAX];
int R, G, Y;
int rp[MAX], gp[MAX], yp[MAX];
int rpref[MAX], gpref[MAX], ypref[MAX];
vector<vector<vector<vi>>> dp;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[i];
		if(arr[i] == 'R') rp[++R] = i, rpref[i] = 1;
		if(arr[i] == 'G') gp[++G] = i, gpref[i] = 1;
		if(arr[i] == 'Y') yp[++Y] = i, ypref[i] = 1;
	}
	
	FOR(i, 1, n, 1){
		rpref[i] = rpref[i-1] + rpref[i];
		gpref[i] = gpref[i-1] + gpref[i];
		ypref[i] = ypref[i-1] + ypref[i];
	}
	
	if(max({R, G, Y}) > (n + 1) / 2){
		cout<<-1<<'\n';
		return 0;
	}
	
	dp.resize(3);
	for(auto& i : dp){
		i.resize(R+1);
		for(auto& j : i){
			j.resize(G+1);
			for(auto& k : j){
				k.resize(Y+1);
				for(int& l : k){
					l = INF;
				}
			}
		}
	}

	dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
	
	FOR(i, 0, R, 1){
		FOR(j, 0, G, 1){
			FOR(k, 0, Y, 1){
				
				if(i > 0){
					int dr = max(gpref[rp[i]] - j, (int)0) + max(ypref[rp[i]] - k, (int)0);
					dp[0][i][j][k] = min({dp[0][i][j][k], dp[1][i-1][j][k] + dr, dp[2][i-1][j][k] + dr});
					//cerr<<"dp[0]["<<i<<"]["<<j<<"]["<<k<<"] = "<<dp[0][i][j][k]<<" ";
				}

				if(j > 0){
					int dg = max(rpref[gp[j]] - i, (int)0) + max(ypref[gp[j]] - k, (int)0);
					dp[1][i][j][k] = min({dp[1][i][j][k], dp[0][i][j-1][k] + dg, dp[2][i][j-1][k] + dg});
					//cerr<<"dp[1]["<<i<<"]["<<j<<"]["<<k<<"] = "<<dp[1][i][j][k]<<" ";
				}

				if(k > 0){
					int dy = max(rpref[yp[k]] - i, (int)0) + max(gpref[yp[k]] - j, (int)0);
					dp[2][i][j][k] = min({dp[2][i][j][k], dp[0][i][j][k-1] + dy, dp[1][i][j][k-1] + dy});
					//cerr<<"dp[2]["<<i<<"]["<<j<<"]["<<k<<"] = "<<dp[2][i][j][k]<<" ";
				}

				//cerr<<endl;

			}
			//cerr<<endl;
		}
	}

	int res = min({dp[0][R][G][Y], dp[1][R][G][Y], dp[2][R][G][Y]});
	cout<<res<<'\n';

	return 0;

}

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