#include <bits/stdc++.h>
using namespace std;
#define int long long
using vi = vector<int>;
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl '\n'
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
template <class T> istream &operator>>(istream& in, vector<T> &v) {for (auto& i : v) in >> i; return in;}
#ifdef LOCAL
#include "../../../lib/debug.h"
#else
#define dbg(...)
#endif
const int N=405,oo=1e18;
int p[3][N];
int cnt[3];
map<char,int>m;
void ckmin(int &a, int b) {
a = min(a, b);
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);m['R']=0;m['G']=1;m['Y']=2;
int n;cin>>n;string s;cin>>s;
FOR(i,0,n)cnt[m[s[i]]]++;
vi y={0,0,0};
FOR(i,0,n){
y[m[s[i]]]++;
p[m[s[i]]][y[m[s[i]]]]=i;
}
int dp[cnt[0]+1][cnt[1]+1][cnt[2]+1][3];
FOR(i,0,cnt[0]+1)FOR(j,0,cnt[1]+1)FOR(k,0,cnt[2]+1)FOR(l,0,3)dp[i][j][k][l]=oo;
// FOR(i,0,3){FOR(j,0,n)cout<<p[i][j]<<' ';cout<<endl;}
FOR(i,0,3)dp[0][0][0][i]=1;
FOR(i,0,cnt[0]+1)FOR(j,0,cnt[1]+1)FOR(k,0,cnt[2]+1)FOR(last,0,3)FOR(next,0,3)if(last!=next){
vi x={i,j,k};if(x[next]==cnt[next])continue;
x[next]++;
ckmin(dp[x[0]][x[1]][x[2]][next],dp[i][j][k][last]+max(0ll,p[next][x[next]]-(i+j+k)));
}
int ans=min({dp[cnt[0]][cnt[1]][cnt[2]][0], dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2]});
if(ans==oo)cout<<-1<<endl;
else cout<<ans-1<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 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 |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 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 |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
5 ms |
1372 KB |
Output is correct |
3 |
Correct |
5 ms |
1368 KB |
Output is correct |
4 |
Correct |
6 ms |
1368 KB |
Output is correct |
5 |
Correct |
7 ms |
1368 KB |
Output is correct |
6 |
Correct |
6 ms |
1372 KB |
Output is correct |
7 |
Correct |
7 ms |
1228 KB |
Output is correct |
8 |
Correct |
7 ms |
1368 KB |
Output is correct |
9 |
Correct |
6 ms |
1372 KB |
Output is correct |
10 |
Correct |
5 ms |
1368 KB |
Output is correct |
11 |
Correct |
6 ms |
1368 KB |
Output is correct |
12 |
Correct |
2 ms |
600 KB |
Output is correct |
13 |
Correct |
3 ms |
860 KB |
Output is correct |
14 |
Correct |
4 ms |
1116 KB |
Output is correct |
15 |
Correct |
6 ms |
1372 KB |
Output is correct |
16 |
Correct |
6 ms |
1368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 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 |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |