제출 #1369031

#제출 시각아이디문제언어결과실행 시간메모리
1369031vjudge1Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
332 ms780436 KiB
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define all(a, len) (a) + 1, (a) + len + 1
#define vall(a) (a).begin(), a.end()
const int INF = 5e8;
const int MOD = 1e9 + 7;

int n; const int mx = 405;
string s;
int dp[mx][mx][mx][3];
int idx[mx][3], nR, nG, nY;
int p[mx][3];
void CONQUEROR() {
    cin >> n >> s;
    s = "#" + s;
    
    for (char c: {'R', 'Y', 'G'}) {
    	if (count(s.begin() + 1, s.end(), c) > (n+1)/2 && n > 1) {
    		cout << -1;
    		exit(0);
    	}
    }
}

void preprocess() {
	nR = nG = nY = 0;
	rep(i, 1, n) {
		rep(j, 0, 2) {
			p[i][j] = (p[i-1][j]);
		}
		if (s[i] == 'R') {
			idx[++nR][0] = i;
			p[i][0]++;
		} else if (s[i] == 'G') {
			idx[++nG][1] = i;
			p[i][1]++;
		} else {
			idx[++nY][2] = i;
			p[i][2]++;
		}
	}
}

inline int cost(int i, int j1, int j2, int col) {
	int u = i - j1 - j2;
	if (col == 0) {
		if (j1 >= nR) return INF;
		int pos = idx[j1 + 1][0];
		int them = 0;
		if (p[pos][1] < j2) them += j2 - p[pos][1];
		if (p[pos][2] < u) them += u - p[pos][2];
		return abs(i + 1 - (pos + them));
	} else if (col == 1) {
		if (j2 >= nG) return INF;
		int pos = idx[j2 + 1][1];
		int them = 0;
		if (p[pos][0] < j1) them += j1 - p[pos][0];
		if (p[pos][2] < u) them += u - p[pos][2];
		return abs(i + 1 - (pos + them));
	} else {
		if (u >= nY) return INF;
		int pos = idx[u + 1][2];
		int them = 0;
		if (p[pos][0] < j1) them += j1 - p[pos][0];
		if (p[pos][1] < j2) them += j2 - p[pos][1];
		return abs(i + 1 - (pos + them));
	}
}

inline void mini(int& x, int y) {
	if (y < x) x = y;
}

void OF() {
	preprocess();
	fill(&dp[0][0][0][0], &dp[0][0][0][0] + mx * mx * mx * 3, INF);
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	
	for (int i = 0; i < n; i++) {
		for (int j1 = 0; j1 <= nR; j1++) {
			for (int j2 = 0; j2 <= nG; j2++) {
				if (i - j1 - j2 > nY) continue;
				for (int t = 0; t <= 2; t++) {
					if (dp[i][j1][j2][t] == INF) continue;
					for (int t_ = 0; t_ <= 2; t_++) if (t_ != t) {
						mini(dp[i + 1][j1 + (t_ == 0)][j2 + (t_ == 1)][t_],
						dp[i][j1][j2][t] + cost(i, j1, j2, t_));
					}
				}
			}
		}
	}
	
	// cerr << dp[1][1][0][0] << endl;
	// cerr << cost(1, 1, 0, 2) << endl;
	// cerr << dp[2][1][0][2] << endl;
	
	int ans = INF;
	rep(t, 0, 2) ans = min(ans, dp[n][nR][nG][t]);
	cout << ans;
}

void DPMQ() {

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int TEST = 1;
    // cin >> TEST;
    while (TEST--) {
        CONQUEROR();
        OF();
        DPMQ();
    }

    return 0;

}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…