Submission #598724

#	Time	Username	Problem	Language	Result	Execution time	Memory
598724		Asymmetry	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	56 ms	29708 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	const int INF = 1e9;
	int n;
	cin >> n;
	map<char, int> s;
	s['R'] = 0;
	s['G'] = 1;
	s['Y'] = 2;
	vector<vector<int>> t(3, vector<int> (1, 0)), sum(3, vector<int> (n + 1, 0));
	vector<int> v(n);
	FOR (i, 1, n) {
		char c;
		cin >> c;
		t[s[c]].emplace_back(i);
		sum[s[c]][i] = 1;
	}
	FOR (i, 1, n) {
		REP (j, 3) {
			sum[j][i] += sum[j][i - 1];
		}
	}
	vector<vector<vector<array<int, 3>>>> dp(sum[0][n] + 1, vector<vector<array<int, 3>>> (sum[1][n] + 1, vector<array<int, 3>> (sum[2][n] + 1, array<int, 3> {INF, INF, INF})));
	REP (i, 3) {
		if (sum[i][n] > (n + 1) / 2) {
			cout << "-1" << endl;
			return 0;
		}
		dp[0][0][0][i] = 0;
	}
	FOR (i, 0, sum[0][n]) {
		FOR (j, 0, sum[1][n]) {
			FOR (k, 0, sum[2][n]) {
				if (i) {
					dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + 
						max(0, sum[1][t[0][i]] - sum[1][t[1][j]]) + 
						max(0, sum[2][t[0][i]] - sum[2][t[2][k]]);
				}
				if (j) {
					dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + 
						max(0, sum[0][t[1][j]] - sum[0][t[0][i]]) + 
						max(0, sum[2][t[1][j]] - sum[2][t[2][k]]);
				}
				if (k) {
					dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + 
						max(0, sum[0][t[2][k]] - sum[0][t[0][i]]) + 
						max(0, sum[1][t[2][k]] - sum[1][t[1][j]]);
				}
			}
		}
	}
	int odp = INF;
	REP (i, 3) {
		odp = min(odp, dp[sum[0][n]][sum[1][n]][sum[2][n]][i]);
	}
	if (odp == INF) {
		cout << "-1" << endl;
		return 0;
	}
	cout << odp << endl;
}

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