Submission #494737

#	Time	Username	Problem	Language	Result	Execution time	Memory
494737		Haruto810198	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	10 ms	6976 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];
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;
		if(arr[i] == 'G') gp[++G] = i;
		if(arr[i] == 'Y') yp[++Y] = 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){
				
				int pos = i + j + k;
				int dr = abs(rp[i] - pos);
				int dg = abs(gp[j] - pos);
				int dy = abs(yp[k] - pos);

				if(i > 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});
				}

				if(j > 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});
				}

				if(k > 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});
				}

			}
		}
	}

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

	return 0;

}

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