Submission #634053

#	Time	Username	Problem	Language	Result	Execution time	Memory
634053		valerikk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	447 ms	781652 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())

using ll = long long;
using ld = long double;

const int N = 405;
const int INF = 0x3f3f3f3f;

int n;
vector<int> v[3];
int invs[3][3][N][N];
int dp[N][N][N][3];

void upd(int &a, int b) {
	a = min(a, b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> n >> s;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'R') v[0].push_back(i);
		if (s[i] == 'G') v[1].push_back(i);
		if (s[i] == 'Y') v[2].push_back(i);
	}
	for (int c1 = 0; c1 < 3; ++c1) {
		for (int c2 = 0; c2 < 3; ++c2) {
			if (c1 == c2) continue;
			for (int i = 0; i < sz(v[c1]); ++i) {
				int cnt = 0;
				for (int j = 0; j <= sz(v[c2]); ++j) {
					invs[c1][c2][i][j] = cnt;
					if (j < sz(v[c2]) && v[c2][j] > v[c1][i]) {
						++cnt;
					}
				}
			}
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	if (sz(v[0]) > 0) {
		dp[1][0][0][0] = 0;
	}
	if (sz(v[1]) > 0) {
		dp[0][1][0][1] = 0;
	}
	if (sz(v[2]) > 0) {
		dp[0][0][1][2] = 0;
	}
	for (int i = 0; i <= sz(v[0]); ++i) {
		for (int j = 0; j <= sz(v[1]); ++j) {
			for (int k = 0; k <= sz(v[2]); ++k) {
				for (int f = 0; f < 3; ++f) {
					if (dp[i][j][k][f] == INF) continue;
					if (i < sz(v[0]) && f != 0) {
						upd(dp[i + 1][j][k][0], dp[i][j][k][f] + invs[0][1][i][j] + invs[0][2][i][k]);
					}
					if (j < sz(v[1]) && f != 1) {
						upd(dp[i][j + 1][k][1], dp[i][j][k][f] + invs[1][0][j][i] + invs[1][2][j][k]);
					}
					if (k < sz(v[2]) && f != 2) {
						upd(dp[i][j][k + 1][2], dp[i][j][k][f] + invs[2][0][k][i] + invs[2][1][k][j]);
					}
				}
			}
		}
	}
	int ans = INF;
	for (int i = 0; i < 3; ++i) {
		ans = min(ans, dp[sz(v[0])][sz(v[1])][sz(v[2])][i]);
	}
	cout << (ans == INF ? -1 : ans) << endl;
	return 0;
}

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