답안 #532000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532000	2022-03-02T03:15:22 Z	abc864197532	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	400 ms	757492 KB

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

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	844 KB	Output is correct
5	Correct	1 ms	1388 KB	Output is correct
6	Correct	1 ms	1344 KB	Output is correct
7	Correct	1 ms	1356 KB	Output is correct
8	Correct	1 ms	1340 KB	Output is correct
9	Correct	1 ms	1356 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	1356 KB	Output is correct
12	Correct	1 ms	1356 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	1228 KB	Output is correct
15	Correct	1 ms	1340 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	844 KB	Output is correct
5	Correct	1 ms	1388 KB	Output is correct
6	Correct	1 ms	1344 KB	Output is correct
7	Correct	1 ms	1356 KB	Output is correct
8	Correct	1 ms	1340 KB	Output is correct
9	Correct	1 ms	1356 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	1356 KB	Output is correct
12	Correct	1 ms	1356 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	1228 KB	Output is correct
15	Correct	1 ms	1340 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	9 ms	18000 KB	Output is correct
19	Correct	8 ms	17988 KB	Output is correct
20	Correct	8 ms	17996 KB	Output is correct
21	Correct	9 ms	17996 KB	Output is correct
22	Correct	10 ms	17912 KB	Output is correct
23	Correct	8 ms	17996 KB	Output is correct
24	Correct	8 ms	17996 KB	Output is correct
25	Correct	1 ms	316 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	8 ms	18028 KB	Output is correct
28	Correct	8 ms	17996 KB	Output is correct
29	Correct	8 ms	17996 KB	Output is correct
30	Correct	8 ms	17980 KB	Output is correct
31	Correct	8 ms	17996 KB	Output is correct
32	Correct	9 ms	17996 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	7 ms	16792 KB	Output is correct
36	Correct	8 ms	17356 KB	Output is correct
37	Correct	8 ms	16204 KB	Output is correct
38	Correct	8 ms	17988 KB	Output is correct
39	Correct	8 ms	17996 KB	Output is correct
40	Correct	1 ms	204 KB	Output is correct
41	Correct	1 ms	204 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	364 ms	757400 KB	Output is correct
3	Correct	344 ms	755140 KB	Output is correct
4	Correct	347 ms	757432 KB	Output is correct
5	Correct	341 ms	757332 KB	Output is correct
6	Correct	356 ms	757492 KB	Output is correct
7	Correct	357 ms	755188 KB	Output is correct
8	Correct	365 ms	755204 KB	Output is correct
9	Correct	372 ms	751452 KB	Output is correct
10	Correct	353 ms	757440 KB	Output is correct
11	Correct	353 ms	757396 KB	Output is correct
12	Correct	92 ms	202736 KB	Output is correct
13	Correct	167 ms	357612 KB	Output is correct
14	Correct	231 ms	517312 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	844 KB	Output is correct
5	Correct	1 ms	1388 KB	Output is correct
6	Correct	1 ms	1344 KB	Output is correct
7	Correct	1 ms	1356 KB	Output is correct
8	Correct	1 ms	1340 KB	Output is correct
9	Correct	1 ms	1356 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	1356 KB	Output is correct
12	Correct	1 ms	1356 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	1228 KB	Output is correct
15	Correct	1 ms	1340 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	9 ms	18000 KB	Output is correct
19	Correct	8 ms	17988 KB	Output is correct
20	Correct	8 ms	17996 KB	Output is correct
21	Correct	9 ms	17996 KB	Output is correct
22	Correct	10 ms	17912 KB	Output is correct
23	Correct	8 ms	17996 KB	Output is correct
24	Correct	8 ms	17996 KB	Output is correct
25	Correct	1 ms	316 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	8 ms	18028 KB	Output is correct
28	Correct	8 ms	17996 KB	Output is correct
29	Correct	8 ms	17996 KB	Output is correct
30	Correct	8 ms	17980 KB	Output is correct
31	Correct	8 ms	17996 KB	Output is correct
32	Correct	9 ms	17996 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	7 ms	16792 KB	Output is correct
36	Correct	8 ms	17356 KB	Output is correct
37	Correct	8 ms	16204 KB	Output is correct
38	Correct	8 ms	17988 KB	Output is correct
39	Correct	8 ms	17996 KB	Output is correct
40	Correct	1 ms	204 KB	Output is correct
41	Correct	1 ms	204 KB	Output is correct
42	Correct	1 ms	324 KB	Output is correct
43	Correct	364 ms	757400 KB	Output is correct
44	Correct	344 ms	755140 KB	Output is correct
45	Correct	347 ms	757432 KB	Output is correct
46	Correct	341 ms	757332 KB	Output is correct
47	Correct	356 ms	757492 KB	Output is correct
48	Correct	357 ms	755188 KB	Output is correct
49	Correct	365 ms	755204 KB	Output is correct
50	Correct	372 ms	751452 KB	Output is correct
51	Correct	353 ms	757440 KB	Output is correct
52	Correct	353 ms	757396 KB	Output is correct
53	Correct	92 ms	202736 KB	Output is correct
54	Correct	167 ms	357612 KB	Output is correct
55	Correct	231 ms	517312 KB	Output is correct
56	Correct	1 ms	324 KB	Output is correct
57	Correct	1 ms	204 KB	Output is correct
58	Correct	385 ms	757332 KB	Output is correct
59	Correct	380 ms	757400 KB	Output is correct
60	Correct	375 ms	751424 KB	Output is correct
61	Correct	381 ms	755244 KB	Output is correct
62	Correct	1 ms	320 KB	Output is correct
63	Correct	358 ms	757316 KB	Output is correct
64	Correct	372 ms	757428 KB	Output is correct
65	Correct	383 ms	755180 KB	Output is correct
66	Correct	400 ms	747724 KB	Output is correct
67	Correct	377 ms	757372 KB	Output is correct
68	Correct	382 ms	755188 KB	Output is correct
69	Correct	375 ms	757340 KB	Output is correct
70	Correct	381 ms	757360 KB	Output is correct
71	Correct	377 ms	755128 KB	Output is correct
72	Correct	1 ms	204 KB	Output is correct
73	Correct	1 ms	204 KB	Output is correct

답안 #532000

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
25.0 / 25.0