oj.uz

Submission #506213

# Submission time Handle Problem Language Result Execution time Memory
506213 2022-01-11T21:47:14 Z sidon Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 96 ms 97064 KB 
#include <bits/stdc++.h>
using namespace std;
#define minim(X, Y) (X = min(X, Y))
#define F(X, Y) for(int X = 0; X < Y; X++)

const int Z = 202, INF = 1e9;

int N, A[Z*2], DP[Z][Z][Z][3], p[3][Z*2], c[3], x, y, z;

int main() {
	cin >> N, getchar();
	F(i, N) {
		char v = getchar();
		A[i] = (v < 82) + (v < 89);
	}

	F(i, Z) F(j, Z) F(k, Z) F(l, 3)
		DP[i][j][k][l] = (i || j || k) ? INF : 0;

	F(i, N) {
		if(++c[A[i]] >= Z-1) break;
		p[A[i]][c[A[i]]] = i + 1;

		F(j, i+1) F(k, i+1) {
			if(A[i] == 0) x = c[0], y = j, z = k;
			if(A[i] == 1) x = j, y = c[1], z = k;
			if(A[i] == 2) x = j, y = k, z = c[2];
			if(x > c[0] || y > c[1] || z > c[2]) continue;
			int s = x + y + z;
			if(x) minim(DP[x][y][z][0], min(DP[x-1][y][z][1], DP[x-1][y][z][2]) + abs(p[0][x] - s));
			if(y) minim(DP[x][y][z][1], min(DP[x][y-1][z][0], DP[x][y-1][z][2]) + abs(p[1][y] - s));
			if(z) minim(DP[x][y][z][2], min(DP[x][y][z-1][0], DP[x][y][z-1][1]) + abs(p[2][z] - s));
		}
	}
	int res = INF;
	F(i, 3) minim(res, DP[c[0]][c[1]][c[2]][i]);
	
	cout << (res == INF ? -1 : res/2);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 97008 KB Output is correct
2 Correct 46 ms 96952 KB Output is correct
3 Correct 45 ms 96936 KB Output is correct
4 Correct 45 ms 96968 KB Output is correct
5 Correct 46 ms 97024 KB Output is correct
6 Correct 44 ms 96964 KB Output is correct
7 Correct 45 ms 97048 KB Output is correct
8 Correct 47 ms 97036 KB Output is correct
9 Correct 45 ms 96964 KB Output is correct
10 Correct 45 ms 96948 KB Output is correct
11 Incorrect 45 ms 96964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 97008 KB Output is correct
2 Correct 46 ms 96952 KB Output is correct
3 Correct 45 ms 96936 KB Output is correct
4 Correct 45 ms 96968 KB Output is correct
5 Correct 46 ms 97024 KB Output is correct
6 Correct 44 ms 96964 KB Output is correct
7 Correct 45 ms 97048 KB Output is correct
8 Correct 47 ms 97036 KB Output is correct
9 Correct 45 ms 96964 KB Output is correct
10 Correct 45 ms 96948 KB Output is correct
11 Incorrect 45 ms 96964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 97024 KB Output is correct
2 Correct 66 ms 97052 KB Output is correct
3 Correct 66 ms 97060 KB Output is correct
4 Correct 96 ms 96956 KB Output is correct
5 Correct 67 ms 97060 KB Output is correct
6 Correct 71 ms 97024 KB Output is correct
7 Correct 70 ms 97000 KB Output is correct
8 Correct 71 ms 97064 KB Output is correct
9 Correct 66 ms 97064 KB Output is correct
10 Correct 67 ms 97060 KB Output is correct
11 Correct 70 ms 97024 KB Output is correct
12 Correct 60 ms 96956 KB Output is correct
13 Correct 52 ms 96980 KB Output is correct
14 Correct 57 ms 97040 KB Output is correct
15 Correct 85 ms 96948 KB Output is correct
16 Correct 68 ms 96964 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 97008 KB Output is correct
2 Correct 46 ms 96952 KB Output is correct
3 Correct 45 ms 96936 KB Output is correct
4 Correct 45 ms 96968 KB Output is correct
5 Correct 46 ms 97024 KB Output is correct
6 Correct 44 ms 96964 KB Output is correct
7 Correct 45 ms 97048 KB Output is correct
8 Correct 47 ms 97036 KB Output is correct
9 Correct 45 ms 96964 KB Output is correct
10 Correct 45 ms 96948 KB Output is correct
11 Incorrect 45 ms 96964 KB Output isn't correct
12 Halted 0 ms 0 KB -