This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
#include <random>
mt19937 rnd(time(0));
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll K = 200;
const ll LOG = 8;
ll dp[210][210][210][3], pref[3][410];
void solve() {
ll n;
cin >> n;
string s;
cin >> s;
s = '#' + s;
map <char, ll> mp;
mp['R'] = 0, mp['G'] = 1, mp['Y'] = 2;
vector <ll> a(n + 1);
for (ll i = 1; i <= n; i++)
a[i] = mp[s[i]];
ll cnt[3] = {0, 0, 0};
for (ll i = 1; i <= n; i++)
cnt[a[i]]++;
if (max({cnt[0], cnt[1], cnt[2]}) > (n + 1) / 2)
return void(cout << -1 << el);
for (ll i = 0; i < 3; i++)
for (ll j = 1; j <= n; j++)
pref[i][j] = pref[i][j - 1] + (a[j] == i);
vector <ll> pos[3];
pos[0].pb(0), pos[1].pb(0), pos[2].pb(0);
for (ll i = 1; i <= n; i++)
pos[a[i]].pb(i);
for (ll i = 0; i <= cnt[0]; i++)
for (ll j = 0; j <= cnt[1]; j++)
for (ll k = 0; k <= cnt[2]; k++)
for (ll cur = 0; cur < 3; cur++)
dp[i][j][k][cur] = inf;
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
for (ll i = 0; i <= cnt[0]; i++)
for (ll j = 0; j <= cnt[1]; j++)
for (ll k = 0; k <= cnt[2]; k++)
for (ll cur = 0; cur < 3; cur++) {
if (i + j + k == 0)
continue;
if (cur == 0) {
if (i == 0)
continue;
ll val = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]);
ll now = pos[cur][i];
now += max(0ll, j - pref[1][pos[cur][i]]);
now += max(0ll, k - pref[2][pos[cur][i]]);
val += now - i - j - k;
dp[i][j][k][cur] = min(dp[i][j][k][cur], val);
}
if (cur == 1) {
if (j == 0)
continue;
ll val = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]);
ll now = pos[cur][j];
now += max(0ll, i - pref[0][pos[cur][j]]);
now += max(0ll, k - pref[2][pos[cur][j]]);
val += now - i - j - k;
dp[i][j][k][cur] = min(dp[i][j][k][cur], val);
}
if (cur == 2) {
if (k == 0)
continue;
ll val = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]);
ll now = pos[cur][k];
now += max(0ll, i - pref[0][pos[cur][k]]);
now += max(0ll, j - pref[1][pos[cur][k]]);
val += now - i - j - k;
dp[i][j][k][cur] = min(dp[i][j][k][cur], val);
}
}
ll 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]});
cout << ans << el;
return;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tests = 1;
//cin >> tests;
while (tests--)
solve();
return 0;
}
/*
*/
# | 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... |