Submission #531989

#	Time	Username	Problem	Language	Result	Execution time	Memory
531989		abc864197532	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	528 ms	757348 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;
	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_cnt = y_num, r_cnt = r_num, g_cnt = g_num;
		int y_nxt = -1, r_nxt = -1, g_nxt = -1, tmp = 0;
		for (char c : s) {
			if (c == 'Y') {
				if (y_cnt)
					y_cnt--;
				else {
					if (y_nxt == -1)
						y_nxt = tmp;
					tmp++;
				}
			} else if (c == 'R') {
				if (r_cnt)
					r_cnt--;
				else {
					if (r_nxt == -1)
						r_nxt = tmp;
					tmp++;
				}
			} else {
				if (g_cnt)
					g_cnt--;
				else {
					if (g_nxt == -1)
						g_nxt = tmp;
					tmp++;
				}
			}
			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: 0 / 15
• Subtask 4: 0 / 25