Submission #532000

#	Time	Username	Problem	Language	Result	Execution time	Memory
532000		abc864197532	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	400 ms	757492 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif
const int N = 401;

int dp[N][N][N][3]; // len, Y num, R num, lst 0Y 1R 2G

int main () {
	owo;
	int n;
	string s;
	cin >> n >> s;
	int bound = n + 1 >> 1;
	int r_all = count(all(s), 'R'), y_all = count(all(s), 'Y'), g_all = count(all(s), 'G');
	if (r_all > bound || y_all > bound || g_all > bound)
		return cout << -1 << '\n', 0;
	for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k)
		dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = 1 << 30;
	vector <int> y_pre(n + 1, 0), r_pre(n + 1, 0), g_pre(n + 1, 0);
	vector <int> Y, R, G;
	for (int i = 0; i < n; ++i) {
		y_pre[i + 1] = y_pre[i] + (s[i] == 'Y');
		r_pre[i + 1] = r_pre[i] + (s[i] == 'R');
		g_pre[i + 1] = g_pre[i] + (s[i] == 'G');
		if (s[i] == 'Y')
			Y.pb(i);
		else if (s[i] == 'R')
			R.pb(i);
		else
			G.pb(i);
	}
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	for (int len = 0; len < n; ++len) for (int y_num = 0; y_num <= len; y_num++) for (int r_num = 0; r_num + y_num <= len; ++r_num) {
		int g_num = len - y_num - r_num;
		if (y_num > y_all || r_num > r_all || g_num > g_all)
			continue;
		int y_nxt = (y_num == y_all ? -1 : max(r_pre[Y[y_num]] - r_num, 0) + max(g_pre[Y[y_num]] - g_num, 0));
		int r_nxt = (r_num == r_all ? -1 : max(y_pre[R[r_num]] - y_num, 0) + max(g_pre[R[r_num]] - g_num, 0));
		int g_nxt = (g_num == g_all ? -1 : max(r_pre[G[g_num]] - r_num, 0) + max(y_pre[G[g_num]] - y_num, 0));
		for (int lst = 0; lst < 3; ++lst) {
			if (y_nxt != -1 && lst != 0)
				dp[len + 1][y_num + 1][r_num][0] = min(dp[len + 1][y_num + 1][r_num][0], dp[len][y_num][r_num][lst] + y_nxt);
			if (r_nxt != -1 && lst != 1)
				dp[len + 1][y_num][r_num + 1][1] = min(dp[len + 1][y_num][r_num + 1][1], dp[len][y_num][r_num][lst] + r_nxt);
			if (g_nxt != -1 && lst != 2)
				dp[len + 1][y_num][r_num][2] = min(dp[len + 1][y_num][r_num][2], dp[len][y_num][r_num][lst] + g_nxt);
		}
	}
	cout << min({dp[n][y_all][r_all][0], dp[n][y_all][r_all][1], dp[n][y_all][r_all][2]}) << '\n';
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:35:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int bound = n + 1 >> 1;
      |              ~~^~~

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