Submission #1326006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326006		tkm_algorithms	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	167 ms	190648 KiB

joi2019_ho_t3

#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;
const int N = 410;
int p[N][3];


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;
		p[j][i] = 1;
	}
	//cout << s << nl;
	
	rep(i, 1, n+1)
		rep(j, 0, 3)
			p[i][j]+=p[i-1][j];
	
	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;
							int gos = 0, pos = g[last][idx-1];
							if (last != 0)gos += min(0, p[pos][0]-zero);
							if (last != 1)gos += min(0, p[pos][1]-bir);
							if (last != 2)gos += min(p[pos][2]-(i-1-zero-bir), 0);
							//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]-gos-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?-1:res) << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
  

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