This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//don't copy pls)
/*TAAK ZDES NADO RECURSIU PISAT*/
//I'm not in the danger i am the DANGER
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define sigma signed
using namespace std;
using namespace __gnu_pbds;
const int N = 400 + 1;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,p[3][N];
vector <int> g[3];
int cnt1 , cnt2 , cnt3;
string s,t;
vector <string> q;
void Gold(){
cin >> n >> s;
s = '+' + s;
t.pb('R');
t.pb('Y');
t.pb('G');
for(int i = 1 ; i <= n ; i++){
if(s[i] == 'R'){
cnt1++;
}
if(s[i] == 'Y'){
cnt2++;
}
if(s[i] == 'G'){
cnt3++;
}
for(int j = 0 ; j < 3 ; j++){
p[j][i] = p[j][i - 1] + (s[i] == t[j]);
}
}
int dp[n + 1][cnt1 + 1][cnt2 + 1][3];
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j <= cnt1 ; j++){
for(int k = 0 ; k <= cnt2 ; k++){
for(int y = 0 ; y < 3 ; y++){
dp[i][j][k][y] = INF;
}
}
}
}
for(int y = 0 ; y < 3 ; y++){
dp[0][0][0][y] = 0;
}
for(int i = 1 ; i <= n ; i++){
for(int j = 0 ; j < 3 ; j++){
if(s[i] == t[j]){
g[j].pb(i);
}
}
}
// cout << "ok";
for(int i = 1 ; i <= n ; i++){
for(int a = 0 ; a <= cnt1 ; a++){
for(int b = 0 ; b <=cnt2 ; b++){
if(a+b>i) continue;
int c = i - (a + b);
if(c > cnt3) continue;
if(a){
int pos = g[0][a - 1];
int cnt = max(0ll,(b - p[1][pos])) + max((c - p[2][pos]) , 0ll);
dp[i][a][b][0] = min(dp[i - 1][a - 1][b][1] , dp[i - 1][a - 1][b][2]) + max(0ll , (pos + cnt) - i);
}
if(b){
int pos = g[1][b - 1];
int cnt = max(a - p[0][pos] , 0ll) + max(c - p[2][pos] , 0ll);
dp[i][a][b][1] = min(dp[i - 1][a][b - 1][0] , dp[i - 1][a][b - 1][2]) + max(0ll , (pos + cnt) - i);
}
if(c){
int pos = g[2][c - 1];
int cnt = max(0ll , a - p[0][pos]) + max(0ll , b - p[1][pos]);
dp[i][a][b][2] = min(dp[i - 1][a][b][0] , dp[i - 1][a][b][1]) + max(0ll , (pos + cnt) - i);
}
// cout << i << ' ' << a << ' ' << b << ' ' << c << '\n';
}
}
}
int ans = INF;
for(int i = 0 ; i < 3 ; i++){
ans = min(ans , dp[n][cnt1][cnt2][i]);
}
if(ans == INF){
cout << "-1\n";
return;
}
cout << ans;
}
sigma main(){
//freopen("txt.in","r",stdin);
//freopen("txt.out","w",stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);
int TT = 1;
// cin >> TT;
for(int i = 1 ; i <= TT ; i++){
//cout << "Case " << i << ": ";
Gold();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |