#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)
#define relax(a, b) a = min(a,b)
int posNow(vvi pos, vvi behind, int c, int i, int R, int G, int Y) {
int p = pos[c][i];
return p+max(0,R-behind[0][p])+max(0,G-behind[1][p])+max(0,Y-behind[2][p]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vi S(N);
string sS;
cin >> sS;
rep(n,0,N) {
switch(sS[n]) {
case 'R': S[n] = 0; break;
case 'G': S[n] = 1; break;
case 'Y': S[n] = 2; break;
}
}
vvi pos(3, vi(0));
rep(n,0,N) pos[S[n]].push_back(n);
vvi behind(3, vi(N+1));
rep(c,0,3) {
int i = 0;
rep(n,0,N+1) {
behind[c][n] = i;
if(i < (int)pos[c].size() && pos[c][i] == n) i++;
}
}
vvvvi steps(N+1, vvvi(N+1, vvi(N+1, vi(3, 1000000000))));
vvvvb vis(N+1, vvvb(N+1, vvb(N+1, vb(3))));
steps[0][0][0][0] = 0;
steps[0][0][0][1] = 0;
steps[0][0][0][2] = 0;
queue<int> q;
q.push(0);
q.push(1);
q.push(2);
while(!q.empty()) {
int front = q.front();
q.pop();
int R = front/3/N/N;
int G = (front/3/N)%N;
int Y = (front/3)%N;
int C = front%3;
int here = steps[R][G][Y][C];
int used = R+G+Y;
if(R < (int)pos[0].size() && !vis[R+1][G][Y][0]) {
vis[R+1][G][Y][0] = true;
q.push((R+1)*N*N*3 + G*N*3 + Y*3 + 0);
}
if(G < (int)pos[1].size() && !vis[R][G+1][Y][1]) {
vis[R][G+1][Y][1] = true;
q.push(R*N*N*3 + (G+1)*N*3 + Y*3 + 1);
}
if(false && Y < (int)pos[2].size() && !vis[R][G][Y+1][2]) {
vis[R][G][Y+1][2] = true;
q.push(R*N*N*3 + G*N*3 + (Y+1)*3 + 2);
}
//cerr << "(R,G,Y,C) = ("<<R<<", "<<G<<", "<<Y<<", "<<C<<") "<<here<<"\n";
if(here == 1000000000) continue;
if(R < (int)pos[0].size() && C != 0) relax(steps[R+1][G][Y][0], here+posNow(pos, behind, 0, R, R, G, Y)-used);
if(G < (int)pos[1].size() && C != 1) relax(steps[R][G+1][Y][1], here+posNow(pos, behind, 1, G, R, G, Y)-used);
if(Y < (int)pos[2].size() && C != 2) relax(steps[R][G][Y+1][2], here+posNow(pos, behind, 2, Y, R, G, Y)-used);
}
int res = 1000000000;
relax(res, steps[(int)pos[0].size()][(int)pos[1].size()][(int)pos[2].size()][0]);
relax(res, steps[(int)pos[0].size()][(int)pos[1].size()][(int)pos[2].size()][1]);
relax(res, steps[(int)pos[0].size()][(int)pos[1].size()][(int)pos[2].size()][2]);
if(res == 1000000000)
cout << "-1\n";
else
cout << res << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Execution timed out |
1127 ms |
792008 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
