oj.uz

Submission #506207

# Submission time Handle Problem Language Result Execution time Memory
506207 2022-01-11T21:24:56 Z sidon Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 172 ms 196640 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) minim(DP[x][y][z][0], min(DP[x-1][y][z][1], DP[x-1][y][z][2]) + abs(p[0][x] - (x + y + z)));
			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] - (x + y + z)));
			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] - (x + y + z)));
		}
	}
	int res = INF;
	F(i, 3) minim(res, DP[c[0]][c[1]][c[2]][i]);
	
	cout << (res > N*N ? -1 : res/2);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97012 KB Output is correct
2 Correct 43 ms 97056 KB Output is correct
3 Correct 44 ms 97092 KB Output is correct
4 Correct 43 ms 97044 KB Output is correct
5 Correct 53 ms 97008 KB Output is correct
6 Correct 43 ms 97000 KB Output is correct
7 Correct 42 ms 97060 KB Output is correct
8 Correct 43 ms 97004 KB Output is correct
9 Incorrect 43 ms 96964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97012 KB Output is correct
2 Correct 43 ms 97056 KB Output is correct
3 Correct 44 ms 97092 KB Output is correct
4 Correct 43 ms 97044 KB Output is correct
5 Correct 53 ms 97008 KB Output is correct
6 Correct 43 ms 97000 KB Output is correct
7 Correct 42 ms 97060 KB Output is correct
8 Correct 43 ms 97004 KB Output is correct
9 Incorrect 43 ms 96964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 97064 KB Output is correct
2 Runtime error 172 ms 196640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97012 KB Output is correct
2 Correct 43 ms 97056 KB Output is correct
3 Correct 44 ms 97092 KB Output is correct
4 Correct 43 ms 97044 KB Output is correct
5 Correct 53 ms 97008 KB Output is correct
6 Correct 43 ms 97000 KB Output is correct
7 Correct 42 ms 97060 KB Output is correct
8 Correct 43 ms 97004 KB Output is correct
9 Incorrect 43 ms 96964 KB Output isn't correct
10 Halted 0 ms 0 KB -