#include <bits/stdc++.h>
using namespace std;
signed main(){
int n; cin >> n;
string s; cin >> s;
//RGY
map<int, vector<int>> pos;
for(int i = 0; i < n; i++)
pos[s[i]].push_back(i);
int dp[n+1][n+1][n+1][3];
for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) for(int l = 0; l < 3; l++){
dp[i][j][k][l] = 1e9;
}
dp[0][0][0][0] = 0;
dp[0][0][0][1] = 0;
dp[0][0][0][2] = 0;
map<char, int> mp;
mp['R']=0, mp['G']=1, mp['Y']=2;
for(int i = 0; i < n; i++){
for(int j = 0; j <= pos['R'].size(); j++){
for(int k = 0; k <= pos['G'].size(); k++){
//printf("%d %d %d\n", i, j, k);
//for(int l: {0, 1, 2}){ printf("dp(%d %d %d %d) = %d\n", i, j, k, l, dp[i][j][k][l]); }
for(char last: {'R', 'G', 'Y'}) for(char next: {'R', 'G', 'Y'}) {
if(last == next) continue;
int x = mp[last], y = mp[next];
//cout << dp[i][j][k][x] << endl;
if(j < pos['R'].size() && next == 'R')
dp[i+1][j+1][k][y] = min(dp[i+1][j+1][k][y], dp[i][j][k][x] + abs(pos[next][j] - i));
if(k < pos['G'].size() && next == 'G')
dp[i+1][j][k+1][y] = min(dp[i+1][j][k+1][y], dp[i][j][k][x] + abs(pos[next][k] - i));
if(i-j-k < pos['Y'].size() && next == 'Y')
dp[i+1][j][k][y] = min(dp[i+1][j][k][y], dp[i][j][k][x] + abs(pos[next][i-j-k] - i));
}
}
}
}
//cout << "here\n";
auto last = dp[n][pos['R'].size()][pos['G'].size()];
int ans = min({last[0], last[1], last[2]});
cout << ((ans == 1e9) ? -1 : ans/2) << endl;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int j = 0; j <= pos['R'].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int k = 0; k <= pos['G'].size(); k++){
| ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(j < pos['R'].size() && next == 'R')
| ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if(k < pos['G'].size() && next == 'G')
| ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(i-j-k < pos['Y'].size() && next == 'Y')
| ~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
1118 ms |
757400 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
436 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
