oj.uz

Submission #252714

# Submission time Handle Problem Language Result Execution time Memory
252714 2020-07-26T07:20:49 Z Mlxa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
5 / 100
 344 ms 379128 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
using ll  = long long;
#define int uint16_t

void umin(int &a, int b) {
	a = min(a, b);
}
void umax(int &a, int b) {
	a = max(a, b);
}

const int N   = 401;
const int INF = UINT8_MAX;

int n;
string str;
int a[N];
int pr[N];
int pg[N];
int py[N];
int wr[N];
int wg[N];
int wy[N];
int dp[N][N][N][3];
// R, G, Y, Last

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> str;
	for (int i = 0; i < n; ++i) {
		pr[i + 1] = pr[i];
		pg[i + 1] = pg[i];
		py[i + 1] = py[i];
		if (str[i] == 'R') {
			a[i] = 0;
			wr[pr[i]] = i;
			++pr[i + 1];
		} else if (str[i] == 'G') {
			a[i] = 1;
			wg[pg[i]] = i;
			++pg[i + 1];
		} else {
			assert(str[i] == 'Y');
			a[i] = 2;
			wy[py[i]] = i;
			++py[i + 1];
		}
	}
	fill_n(dp[0][0][0], 3 * N * N * N, INF);
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for (int r = 0; r <= pr[n]; ++r) {
		for (int g = 0; g <= pg[n]; ++g) {
			for (int y = 0; y <= py[n]; ++y) {
				for (int l = 0; l < 3; ++l) {
					int v = dp[r][g][y][l];
					if (v >= INF) {
						continue;
					}
					if (l != 0 && r < pr[n]) {
						int i = wr[r];
						umin(dp[r + 1][g][y][0], v + abs(pg[i] - g) + abs(py[i] - y));
					}
					if (l != 1 && g < pg[n]) {
						int i = wg[g];
						umin(dp[r][g + 1][y][1], v + abs(pr[i] - r) + abs(py[i] - y));
					}
					if (l != 2 && y < py[n]) {
						int i = wy[y];
						umin(dp[r][g][y + 1][2], v + abs(pr[i] - r) + abs(pg[i] - g));
					}
				}
			}
		}
	}
	int r = pr[n], g = pg[n], y = py[n];
	int ans = min(min(dp[r][g][y][0], dp[r][g][y][1]), dp[r][g][y][2]);
	if (ans >= INF) {
		cout << "-1\n";
		return 0;
	}
	assert(ans % 2 == 0);
	cout << ans / 2 << "\n";
    return 0;
}

/**
RRGYY
->
RYRGY
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 378872 KB Output is correct
2 Correct 322 ms 378860 KB Output is correct
3 Correct 312 ms 378884 KB Output is correct
4 Correct 319 ms 379000 KB Output is correct
5 Correct 316 ms 379000 KB Output is correct
6 Correct 316 ms 378920 KB Output is correct
7 Correct 317 ms 378968 KB Output is correct
8 Correct 340 ms 378940 KB Output is correct
9 Correct 331 ms 378872 KB Output is correct
10 Correct 318 ms 378872 KB Output is correct
11 Correct 318 ms 378872 KB Output is correct
12 Correct 309 ms 378932 KB Output is correct
13 Correct 327 ms 379000 KB Output is correct
14 Correct 310 ms 378824 KB Output is correct
15 Correct 324 ms 378872 KB Output is correct
16 Correct 316 ms 378872 KB Output is correct
17 Correct 321 ms 379128 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 378872 KB Output is correct
2 Correct 322 ms 378860 KB Output is correct
3 Correct 312 ms 378884 KB Output is correct
4 Correct 319 ms 379000 KB Output is correct
5 Correct 316 ms 379000 KB Output is correct
6 Correct 316 ms 378920 KB Output is correct
7 Correct 317 ms 378968 KB Output is correct
8 Correct 340 ms 378940 KB Output is correct
9 Correct 331 ms 378872 KB Output is correct
10 Correct 318 ms 378872 KB Output is correct
11 Correct 318 ms 378872 KB Output is correct
12 Correct 309 ms 378932 KB Output is correct
13 Correct 327 ms 379000 KB Output is correct
14 Correct 310 ms 378824 KB Output is correct
15 Correct 324 ms 378872 KB Output is correct
16 Correct 316 ms 378872 KB Output is correct
17 Correct 321 ms 379128 KB Output is correct
18 Correct 315 ms 378872 KB Output is correct
19 Correct 321 ms 378872 KB Output is correct
20 Correct 315 ms 378992 KB Output is correct
21 Correct 329 ms 378872 KB Output is correct
22 Correct 317 ms 378872 KB Output is correct
23 Correct 306 ms 378872 KB Output is correct
24 Correct 336 ms 378888 KB Output is correct
25 Correct 344 ms 378932 KB Output is correct
26 Correct 340 ms 378976 KB Output is correct
27 Incorrect 327 ms 379000 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 378872 KB Output is correct
2 Incorrect 335 ms 378872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 378872 KB Output is correct
2 Correct 322 ms 378860 KB Output is correct
3 Correct 312 ms 378884 KB Output is correct
4 Correct 319 ms 379000 KB Output is correct
5 Correct 316 ms 379000 KB Output is correct
6 Correct 316 ms 378920 KB Output is correct
7 Correct 317 ms 378968 KB Output is correct
8 Correct 340 ms 378940 KB Output is correct
9 Correct 331 ms 378872 KB Output is correct
10 Correct 318 ms 378872 KB Output is correct
11 Correct 318 ms 378872 KB Output is correct
12 Correct 309 ms 378932 KB Output is correct
13 Correct 327 ms 379000 KB Output is correct
14 Correct 310 ms 378824 KB Output is correct
15 Correct 324 ms 378872 KB Output is correct
16 Correct 316 ms 378872 KB Output is correct
17 Correct 321 ms 379128 KB Output is correct
18 Correct 315 ms 378872 KB Output is correct
19 Correct 321 ms 378872 KB Output is correct
20 Correct 315 ms 378992 KB Output is correct
21 Correct 329 ms 378872 KB Output is correct
22 Correct 317 ms 378872 KB Output is correct
23 Correct 306 ms 378872 KB Output is correct
24 Correct 336 ms 378888 KB Output is correct
25 Correct 344 ms 378932 KB Output is correct
26 Correct 340 ms 378976 KB Output is correct
27 Incorrect 327 ms 379000 KB Output isn't correct
28 Halted 0 ms 0 KB -