#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar2 = array<ll,2>;
const int N = (int)4e2+10;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
vi v[3];
string s;
int n, cnt[3];
int dp[N][3][N/2][N];
int8_t dp2[3][3][N][N][N];
int num(int cnt0, int cnt1, int cnt2, int f0, int f1, int f2){
if(!cnt0) return 0;
//if(dp2[f0][f1][cnt0][cnt1][cnt2]!=-1)
// return dp2[f0][f1][cnt0][cnt1][cnt2];
int n1 = 0, n2 = 0, XD = v[f0][cnt0-1];
if(cnt1 and v[f1][cnt1-1] > XD){
int pos = lower_bound(all(v[f1]),XD)-begin(v[f1]);
n1 = cnt1-pos;
}
if(cnt2 and v[f2][cnt2-1] > XD){
int pos = lower_bound(all(v[f2]),XD)-begin(v[f2]);
n2 = cnt2-pos;
}
return dp2[f0][f1][cnt0][cnt1][cnt2]=n1+n2;
}
void swp(int i, int j){
swap(cnt[i],cnt[j]); swap(v[i],v[j]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++){
char u = s[i];
if(u=='R') s[i]=0;
else if(u=='G') s[i]=1;
else s[i]=2;
cnt[s[i]]++; v[s[i]].pb(i+1);
}
if(cnt[0]>cnt[1])swp(0,1);
if(cnt[1]>cnt[2])swp(1,2);
if(cnt[0]>cnt[1])swp(0,1);
memset(dp,0x3f3f3f3f,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
if(cnt[0]) dp[1][0][1][0] = v[0][0]-1;
if(cnt[1]) dp[1][1][0][1] = v[1][0]-1;
if(cnt[2]) dp[1][2][0][0] = v[2][0]-1;
int ans = INF;
for(int i = 2; i <= n; i++){
for(int j = 0; j < 3; j++){
for(int m = 0; m < 3; m++){
if(m==j) continue;
for(int k = 0; k <= min(i,cnt[0]); k++){
for(int l = 0; l <= min(i,cnt[1]); l++){
int o = i-k-l; if(o>i or o>cnt[2]) continue;
if(k and j==0){
int f0 = v[0][k-1]+num(k,l,o,0,1,2);
if(f0>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k-1][l]+f0-i);
}
if(l and j==1){
int f1 = v[1][l-1]+num(l,k,o,1,0,2);
if(f1>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l-1]+f1-i);
}
if(o and j==2){
int f2 = v[2][o-1]+num(o,k,l,2,0,1);
if(f2>=i) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i-1][m][k][l]+f2-i);
}
}
}
}
}
}
for(int j = 0; j < 3; j++)
for(int k = 0; k <= cnt[0]; k++)
for(int l = 0; l <= cnt[1]; l++)
ans = min(ans, dp[n][j][k][l]);
if(ans>=INF) ans=-1;
cout << ans << "\n";
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:50:11: warning: array subscript has type 'char' [-Wchar-subscripts]
50 | cnt[s[i]]++; v[s[i]].pb(i+1);
| ^
joi2019_ho_t3.cpp:50:22: warning: array subscript has type 'char' [-Wchar-subscripts]
50 | cnt[s[i]]++; v[s[i]].pb(i+1);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
759 ms |
1011920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
759 ms |
1011920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
733 ms |
1011936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
759 ms |
1011920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
