oj.uz

Submission #817660

# Submission time Handle Problem Language Result Execution time Memory
817660 2023-08-09T14:44:55 Z Zanite Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 500 ms 386872 KB 
#include <bits/stdc++.h>
using namespace std;

array<int, 255> colorCode;
const int iINF	= 1e9;
const int maxN	= 423;

int N, cnt[3], color[maxN], pos[3][maxN], pf[3][maxN];
int dp[maxN][maxN][maxN][3];

int query(int clr, int pos, int maxIdx) {
	return max(0, pf[clr][pos] - maxIdx);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	colorCode['R'] = 0;
	colorCode['G'] = 1;
	colorCode['Y'] = 2;

	cin >> N;
	char buf;
	for (int i = 1; i <= N; i++) {
		cin >> buf;
		color[i] = colorCode[buf];
	}

	int &R = cnt[0];
	int &G = cnt[1];
	int &Y = cnt[2];
	for (int i = 1; i <= N; i++) {
		pos[color[i]][++cnt[color[i]]] = i;
		for (int j = 0; j <= 2; j++) {
			pf[j][i] = pf[j][i-1] + (color[i] == j);
		}
	}

	// for (int j = 0; j <= 2; j++) {
	// 	for (int i = 1; i <= N; i++) cout << pos[j][i] << ' ';
	// 	cout << '\n';
	// 	for (int i = 1; i <= N; i++) cout << pf[j][i] << ' ';
	// 	cout << '\n';
	// 	cout << '\n';
	// }

	// dp[r][g][y][lst] = number of swaps to the left that must be done
	// to get r red, g green, and y yellow with last color lst
	for (int n = 1; n <= N; n++) {
		array<int, 3> lpos;
		int &r = lpos[0];
		int &g = lpos[1];
		int &y = lpos[2];

		for (r = 0; r <= n; r++) {
			for (g = 0; g <= n-r; g++) {
				y = n-r-g;
				for (int lst = 0; lst <= 2; lst++) {
					if (!lpos[lst]) {
						dp[r][g][y][lst] = iINF;
						continue;
					}

					int prv = iINF;
					lpos[lst]--;
					for (int plst = 0; plst <= 2; plst++) {
						if (plst == lst) continue;
						prv = min(prv, dp[r][g][y][plst]);
					}
					lpos[lst]++;

					int swaps = 0;
					for (int i = 0; i <= 2; i++) {
						if (i == lst) continue;
						swaps += query(i, pos[lst][lpos[lst]], lpos[i]);
					}

					dp[r][g][y][lst] = min(iINF, prv + swaps);
					// fprintf(stderr, "dp[%d][%d][%d][%d] = %d\n", r, g, y, lst, dp[r][g][y][lst]);
				}
			}
		}
	}

	int ans = iINF;
	for (int lst = 0; lst <= 2; lst++) ans = min(ans, dp[R][G][Y][lst]);
	if (ans == iINF) ans = -1;
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 4 ms 8532 KB Output is correct
20 Correct 4 ms 8532 KB Output is correct
21 Correct 4 ms 8524 KB Output is correct
22 Correct 4 ms 8532 KB Output is correct
23 Correct 4 ms 8512 KB Output is correct
24 Correct 5 ms 8532 KB Output is correct
25 Correct 4 ms 8524 KB Output is correct
26 Correct 4 ms 8532 KB Output is correct
27 Correct 4 ms 8532 KB Output is correct
28 Correct 4 ms 8532 KB Output is correct
29 Correct 6 ms 8524 KB Output is correct
30 Correct 4 ms 8532 KB Output is correct
31 Correct 4 ms 8532 KB Output is correct
32 Correct 5 ms 8532 KB Output is correct
33 Correct 4 ms 8268 KB Output is correct
34 Correct 6 ms 8296 KB Output is correct
35 Correct 4 ms 8020 KB Output is correct
36 Correct 4 ms 8264 KB Output is correct
37 Correct 5 ms 7764 KB Output is correct
38 Correct 5 ms 8532 KB Output is correct
39 Correct 5 ms 8532 KB Output is correct
40 Correct 4 ms 8276 KB Output is correct
41 Correct 5 ms 8532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 768 ms 386872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 4 ms 8532 KB Output is correct
20 Correct 4 ms 8532 KB Output is correct
21 Correct 4 ms 8524 KB Output is correct
22 Correct 4 ms 8532 KB Output is correct
23 Correct 4 ms 8512 KB Output is correct
24 Correct 5 ms 8532 KB Output is correct
25 Correct 4 ms 8524 KB Output is correct
26 Correct 4 ms 8532 KB Output is correct
27 Correct 4 ms 8532 KB Output is correct
28 Correct 4 ms 8532 KB Output is correct
29 Correct 6 ms 8524 KB Output is correct
30 Correct 4 ms 8532 KB Output is correct
31 Correct 4 ms 8532 KB Output is correct
32 Correct 5 ms 8532 KB Output is correct
33 Correct 4 ms 8268 KB Output is correct
34 Correct 6 ms 8296 KB Output is correct
35 Correct 4 ms 8020 KB Output is correct
36 Correct 4 ms 8264 KB Output is correct
37 Correct 5 ms 7764 KB Output is correct
38 Correct 5 ms 8532 KB Output is correct
39 Correct 5 ms 8532 KB Output is correct
40 Correct 4 ms 8276 KB Output is correct
41 Correct 5 ms 8532 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Execution timed out 768 ms 386872 KB Time limit exceeded
44 Halted 0 ms 0 KB -