# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
99261 | 2019-03-02T03:19:26 Z | imeimi2000 | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 29 ms | 1152 KB |
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int inf = 1e7; int n; char str[401]; int tr[256]; vector<int> pos[3]; int dp[401][401][3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); tr['R'] = 0; tr['G'] = 1; tr['Y'] = 2; cin >> n >> str; for (int i = 0; i < n; ++i) pos[tr[str[i]]].push_back(i + 1); for (int j = 0; j <= pos[1].size(); ++j) { for (int k = 0; k <= pos[2].size(); ++k) { if (j + k == 0) continue; for (int l = 0; l < 3; ++l) dp[j][k][l] = inf; } } for (int i = 0; i <= pos[0].size(); ++i) { for (int j = 0; j <= pos[1].size(); ++j) { for (int k = 0; k <= pos[2].size(); ++k) { if (i + j + k == 0) continue; if (i) dp[j][k][0] = min(dp[j][k][1], dp[j][k][2]) + abs(i + j + k - pos[0][i - 1]); else dp[j][k][0] = inf; if (j) dp[j][k][1] = min(dp[j - 1][k][0], dp[j - 1][k][2]) + abs(i + j + k - pos[1][j - 1]); else dp[j][k][1] = inf; if (k) dp[j][k][2] = min(dp[j][k - 1][0], dp[j][k - 1][1]) + abs(i + j + k - pos[2][k - 1]); else dp[j][k][2] = inf; } } } int ans = inf; for (int i = 0; i < 3; ++i) ans = min(ans, dp[pos[1].size()][pos[2].size()][i]); printf("%d\n", ans < inf ? ans / 2 : -1); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Incorrect | 3 ms | 384 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Incorrect | 3 ms | 384 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1152 KB | Output is correct |
4 | Correct | 4 ms | 1152 KB | Output is correct |
5 | Correct | 3 ms | 1152 KB | Output is correct |
6 | Correct | 29 ms | 1152 KB | Output is correct |
7 | Correct | 4 ms | 1152 KB | Output is correct |
8 | Correct | 4 ms | 1152 KB | Output is correct |
9 | Correct | 3 ms | 1152 KB | Output is correct |
10 | Correct | 4 ms | 1152 KB | Output is correct |
11 | Correct | 3 ms | 1152 KB | Output is correct |
12 | Correct | 2 ms | 768 KB | Output is correct |
13 | Correct | 3 ms | 896 KB | Output is correct |
14 | Correct | 4 ms | 1024 KB | Output is correct |
15 | Correct | 3 ms | 1152 KB | Output is correct |
16 | Correct | 3 ms | 1152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 3 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Incorrect | 3 ms | 384 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |