# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
99010 | 2019-02-28T05:24:01 Z | ainta | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 377 ms | 378720 KB |
#include<cstdio> #include<algorithm> #include<vector> using namespace std; int n, Num[200], C[3]; vector<int>U[3]; char p[410]; int D[410][410][410][3]; int main() { int i, j, k; Num['R'] = 0; Num['G'] = 1; Num['Y'] = 2; scanf("%d", &n); scanf("%s", p + 1); for (i = 1; i <= n; i++) { U[Num[p[i]]].push_back(i); } for (i = 0; i < 3; i++)C[i] = U[i].size(); for (i = 0; i <= n; i++) { for (j = 0; j <= i; j++) { for (k = 0; j+k <= i; k++) { D[i][j][k][0]=D[i][j][k][1]=D[i][j][k][2] = 1e9; } } } D[1][1][0][0] = (Num[p[1]] != 0); D[1][0][1][1] = (Num[p[1]] != 1); D[1][0][0][2] = (Num[p[1]] != 2); for (i = 1; i < n; i++) { for (j = 0; j <= i; j++) { for (k = 0; j+k <= i; k++) { int l = i - j - k; if (j > C[0] || k > C[1] || l > C[2])continue; for (int ii = 0; ii < 3; ii++) { int t = D[i][j][k][ii]; if (t > 1e8)continue; if (ii!=0 && j != C[0]) { D[i + 1][j + 1][k][0] = min(D[i + 1][j + 1][k][0], t + abs(U[0][j] - (i + 1))); } if (ii!=1 && k != C[1]) { D[i + 1][j][k + 1][1] = min(D[i + 1][j][k + 1][1], t + abs(U[1][k] - (i + 1))); } if (ii!=2 && l != C[2]) { D[i + 1][j][k][2] = min(D[i + 1][j][k][2], t + abs(U[2][l] - (i + 1))); } } } } } int res = 1e9; for (i = 0; i < 3; i++) { res = min(res, D[n][C[0]][C[1]][i]); } if (res > 1e8) { puts("-1"); } else { printf("%d\n", res / 2); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 896 KB | Output is correct |
6 | Correct | 3 ms | 896 KB | Output is correct |
7 | Incorrect | 2 ms | 896 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 896 KB | Output is correct |
6 | Correct | 3 ms | 896 KB | Output is correct |
7 | Incorrect | 2 ms | 896 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 377 ms | 378720 KB | Output is correct |
3 | Correct | 338 ms | 376824 KB | Output is correct |
4 | Correct | 365 ms | 378672 KB | Output is correct |
5 | Correct | 305 ms | 378616 KB | Output is correct |
6 | Incorrect | 316 ms | 378680 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 3 ms | 896 KB | Output is correct |
6 | Correct | 3 ms | 896 KB | Output is correct |
7 | Incorrect | 2 ms | 896 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |