# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
98276 | 2019-02-21T18:59:03 Z | someone_aa | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 124 ms | 164984 KB |
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 410; const int inf = 100000000; int dp[maxn][maxn][maxn][3]; int n, arr[maxn]; string code; vector<int>v[3]; int main() { cin>>n; cin>>code; for(int i=0;i<code.length();i++) { if(code[i] == 'R') arr[i + 1] = 0; else if(code[i] == 'G') arr[i + 1] = 1; else arr[i + 1] = 2; v[arr[i+1]].pb(i + 1); } for(int i=0;i<=v[0].size()+1;i++) { for(int j=0;j<=v[1].size()+1;j++) { for(int k=0;k<=v[2].size()+1;k++) { for(int l=0;l<=2;l++) { dp[i][j][k][l] = inf; } } } } dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; for(int c0=0;c0<=v[0].size();c0++) { for(int c1=0;c1<=v[1].size();c1++) { for(int c2=0;c2<=v[2].size();c2++) { for(int last=0;last<=2;last++) { if(dp[c0][c1][c2][last] == inf) continue; for(int nxt=0;nxt<=2;nxt++) { if(last != 0 && nxt == 0 && c0 < v[0].size()) { dp[c0+1][c1][c2][0] = min(dp[c0+1][c1][c2][0], dp[c0][c1][c2][last] + abs(v[0][c0] - (c0+c1+c2+1))); } else if(last != 1 && nxt == 1 && c1 < v[1].size()) { dp[c0][c1+1][c2][1] = min(dp[c0][c1+1][c2][1], dp[c0][c1][c2][last] + abs(v[1][c1] - (c0+c1+c2+1))); } else if(last != 2 && nxt == 2 && c2 < v[2].size()) { dp[c0][c1][c2+1][2] = min(dp[c0][c1][c2+1][2], dp[c0][c1][c2][last] + abs(v[2][c2] - (c0+c1+c2+1))); } } } } } } int result = min(min(dp[v[0].size()][v[1].size()][v[2].size()][0], dp[v[0].size()][v[1].size()][v[2].size()][1]), dp[v[0].size()][v[1].size()][v[2].size()][2]); if(result == inf) { cout<<"-1\n"; return 0; } cout<<(result/2)<<"\n"; 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 | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 768 KB | Output is correct |
11 | Incorrect | 2 ms | 640 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 | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 768 KB | Output is correct |
11 | Incorrect | 2 ms | 640 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 | 124 ms | 164928 KB | Output is correct |
3 | Correct | 121 ms | 164216 KB | Output is correct |
4 | Correct | 123 ms | 164924 KB | Output is correct |
5 | Correct | 120 ms | 164956 KB | Output is correct |
6 | Correct | 120 ms | 164984 KB | Output is correct |
7 | Correct | 119 ms | 164088 KB | Output is correct |
8 | Correct | 117 ms | 164088 KB | Output is correct |
9 | Correct | 123 ms | 163448 KB | Output is correct |
10 | Correct | 118 ms | 164984 KB | Output is correct |
11 | Correct | 123 ms | 164984 KB | Output is correct |
12 | Correct | 33 ms | 45048 KB | Output is correct |
13 | Correct | 60 ms | 78444 KB | Output is correct |
14 | Correct | 82 ms | 113016 KB | Output is correct |
15 | Correct | 121 ms | 164956 KB | Output is correct |
16 | Correct | 122 ms | 164892 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 | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 640 KB | Output is correct |
10 | Correct | 2 ms | 768 KB | Output is correct |
11 | Incorrect | 2 ms | 640 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |