# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
428287 | 2021-06-15T09:39:54 Z | Berted | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++14 | 332 ms | 7876 KB |
#include <iostream> #include <vector> #define ll long long using namespace std; const ll INF = 1e18; int N; string S; vector<int> A[3]; ll DP[2][3][401][401]; int main() { cin >> N >> S; for (int i = 1; i <= N; i++) { if (S[i - 1] == 'R') {A[0].push_back(i);} else if (S[i - 1] == 'G') {A[1].push_back(i);} else {A[2].push_back(i);} } for (int s = 0; s < 3; s++) for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) DP[0][s][i][j] = INF; for (int s = 0; s < 3; s++) DP[0][s][0][0] = 0; for (int i = 1; i <= N; i++) { for (int s = 0; s < 3; s++) for (int j = 0; j <= N; j++) for (int k = 0; k <= N; k++) DP[i & 1][s][j][k] = INF; for (int s = 0; s < 3; s++) { for (int j = 0; j <= i && j <= A[0].size(); j++) { for (int k = 0; k + j <= i && k <= A[1].size(); k++) { int l = i - j - k; if (l > A[2].size()) continue; if (s == 0 && j) { for (int t = 0; t < 3; t++) { if (s == t) continue; DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j - 1][k] + max(0, A[s][j - 1] - i)); } } if (s == 1 && k) { for (int t = 0; t < 3; t++) { if (s == t) continue; DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k - 1] + max(0, A[s][k - 1] - i)); } } if (s == 2 && l) { for (int t = 0; t < 3; t++) { if (s == t) continue; DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k] + max(0, A[s][l - 1] - i)); } } //if (DP[i & 1][s][j][k] < INF) cout << i << " " << s << " " << j << " " << k << " " << l << " " << DP[i & 1][s][j][k] << "\n"; } } } } ll res = INF; for (int s = 0; s < 3; s++) {res = min(res, DP[N & 1][s][A[0].size()][A[1].size()]);} if (res == INF) cout << "-1\n"; else { cout << res << "\n"; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 460 KB | Output is correct |
5 | Correct | 1 ms | 588 KB | Output is correct |
6 | Correct | 1 ms | 560 KB | Output is correct |
7 | Correct | 1 ms | 556 KB | Output is correct |
8 | Correct | 1 ms | 588 KB | Output is correct |
9 | Correct | 1 ms | 588 KB | Output is correct |
10 | Correct | 1 ms | 588 KB | Output is correct |
11 | Incorrect | 1 ms | 560 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 460 KB | Output is correct |
5 | Correct | 1 ms | 588 KB | Output is correct |
6 | Correct | 1 ms | 560 KB | Output is correct |
7 | Correct | 1 ms | 556 KB | Output is correct |
8 | Correct | 1 ms | 588 KB | Output is correct |
9 | Correct | 1 ms | 588 KB | Output is correct |
10 | Correct | 1 ms | 588 KB | Output is correct |
11 | Incorrect | 1 ms | 560 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 317 ms | 7828 KB | Output is correct |
3 | Correct | 268 ms | 7756 KB | Output is correct |
4 | Correct | 266 ms | 7840 KB | Output is correct |
5 | Correct | 275 ms | 7876 KB | Output is correct |
6 | Correct | 269 ms | 7828 KB | Output is correct |
7 | Correct | 324 ms | 7748 KB | Output is correct |
8 | Correct | 265 ms | 7844 KB | Output is correct |
9 | Correct | 323 ms | 7824 KB | Output is correct |
10 | Correct | 281 ms | 7844 KB | Output is correct |
11 | Correct | 286 ms | 7756 KB | Output is correct |
12 | Correct | 39 ms | 4172 KB | Output is correct |
13 | Correct | 95 ms | 5572 KB | Output is correct |
14 | Correct | 183 ms | 6536 KB | Output is correct |
15 | Correct | 332 ms | 7836 KB | Output is correct |
16 | Correct | 282 ms | 7832 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 460 KB | Output is correct |
5 | Correct | 1 ms | 588 KB | Output is correct |
6 | Correct | 1 ms | 560 KB | Output is correct |
7 | Correct | 1 ms | 556 KB | Output is correct |
8 | Correct | 1 ms | 588 KB | Output is correct |
9 | Correct | 1 ms | 588 KB | Output is correct |
10 | Correct | 1 ms | 588 KB | Output is correct |
11 | Incorrect | 1 ms | 560 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |