#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
signed main(){
int n; cin >> n;
string s; cin >> s;
//RGY
map<char, int> mp;
mp['R']=0, mp['G']=1, mp['Y']=2;
vector<int> a(n);
for(int i = 0; i < n; i++) a[i] = mp[s[i]];
array<vector<int>, 3> pos;
for(int i = 0; i < n; i++)
pos[a[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;
for(int i = 0; i < n; i++){
for(int j = 0; j <= pos[0].size(); j++){
for(int k = 0; k <= pos[1].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(int last: {0, 1, 2}) for(int next: {0, 1, 2}) {
if(last == next) continue;
int x = last, y = next;
//cout << last << " " << next << " ";
//cout << x << " " << y << endl;
//cout << dp[i][j][k][x] << endl;
if(j < pos[0].size() && next == 0)
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[1].size() && next == 1)
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[2].size() && next == 2)
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[0].size()][pos[1].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:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int j = 0; j <= pos[0].size(); j++){
| ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int k = 0; k <= pos[1].size(); k++){
| ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if(j < pos[0].size() && next == 0)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if(k < pos[1].size() && next == 1)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if(i-j-k < pos[2].size() && next == 2)
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 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 |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 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 |
Execution timed out |
558 ms |
757528 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
