제출 #1325386

#제출 시각아이디문제언어결과실행 시간메모리
1325386tkm_algorithmsGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
15 / 100
100 ms190612 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9;

void mnu(int &a, int b) {
	if (a>b || a == -1)a=b;
}

void solve() {
	int n; cin >> n;
	string s; cin >> s; s = '&'+s;
	deque<int> g[3];
	rep(i, 1, n+1) {
		if (s[i] == 'R')g[0].push_back(i);
		else if (s[i] == 'G')g[1].push_back(i);
		else g[2].push_back(i);
	}
	
	vector<int> vis(n+1, 2);
	if (sz(g[0]) > sz(g[2]))swap(g[0], g[2]);
	if (sz(g[0]) > sz(g[1]))swap(g[0], g[1]);
	if (sz(g[1]) > sz(g[2]))swap(g[1], g[2]);
	
	int dp[n+1][3][201][201];
	memset(dp, -1, sizeof dp);
	
	rep(i, 0, 3)
		for (auto j: g[i])s[j] = char(i+'0'), vis[j] = i;
	
	//cout << s << nl;
	rep(i, 0, 3)
		if (sz(g[i])>0)dp[1][i][i==0][i==1] = g[i][0]-1;
	
	int a = sz(g[0]), b = sz(g[1]);
	rep(i, 1, n+1) {
		//dp[i][s[i]-'0'][(vis[i]==0)][(vis[i]==1)] = 0;
		rep(pre_last, 0, 3) {
			rep(zero, 0, min(i, sz(g[0])+1))
				rep(bir, 0, min(i, sz(g[1])+1)) {
					if (bir+zero>=i)break;
					if (dp[i-1][pre_last][zero][bir] ==-1)continue;
					if (sz(g[2]) < i-1-zero-bir)continue;
					rep(last, 0, 3)
						if (last != pre_last) {
							int idx = (last==0?zero+1:0)+(last==1?bir+1:0)+(last==2?i-zero-bir:0);
							if (sz(g[last])<idx)continue;
							//assert(zero+bir+idx==i);
							mnu(dp[i][last][zero+(last==0)][bir+(last==1)], dp[i-1][pre_last][zero][bir]+abs(g[last][idx-1]-i));
						}
				}
		}
	}
	
	int res = inf;
	rep(i, 0, 3)
		rep(zero, 0, a+1)
			rep(bir, 0, b+1) {
				//if (dp[n][i][zero][bir])cout << i << " " << zero << " " << bir << nl;
				if (~dp[n][i][zero][bir])res = min(res, dp[n][i][zero][bir]);
			}
			
	cout << (res==inf?-3:res+1)/2 << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
  
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...