#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 4e2 + 7;
const ll oo = 1e9 + 69;
int n;
char a[maxn];
struct sub2 {
int dp[maxn][maxn][maxn][3];
int cost[maxn][maxn][3], f[maxn][3];
char b[maxn];
int calc(char ch, int l, int r) {
for(int i = l; i <= r; i++) b[i] = a[i];
int ans = 0;
for(int i = l; i <= r; i++) {
if(i % 2 == l % 2 && b[i] != ch) {
bool ok = 0;
for(int j = i + 1; j <= r; j++) {
if(b[j] == ch) {
ok = 1;
for(int k = j; k > i; k--) {
ans++;
swap(b[k], b[k - 1]);
}
break;
}
}
if(!ok) return oo;
}
if(i % 2 != l % 2 && b[i] == ch) {
bool ok = 0;
for(int j = i + 1; j <= r; j++) {
if(b[j] != ch) {
ok = 1;
for(int k = j; k > i; k--) {
ans++;
swap(b[k], b[k - 1]);
}
break;
}
}
if(!ok) return oo;
}
}
return ans;
}
void compute(int l, int r) {
vector<char> ch;
for(int i = l; i <= r; i++) ch.pb(a[i]);
sort(all(ch));
ch.erase(unique(all(ch)), ch.end());
if(Size(ch) == 3) return;
int ans = oo;
int t;
if(l % 2 == r % 2) t = convert(ch.front());
else t = convert(ch.back());
cost[l][r][t] = calc(ch.front(), l, r);
if(l % 2 == r % 2) t = convert(ch.back());
else t = convert(ch.front());
cost[l][r][t] = calc(ch.back(), l, r);
}
int convert(char ch) {
if(ch == 'R') return 0;
if(ch == 'G') return 1;
return 2;
}
void solve() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int cur = 0; cur < 3; cur++) cost[i][j][cur] = oo;
}
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
compute(i, j);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) f[i][j] = f[i - 1][j];
f[i][convert(a[i])]++;
}
for(int i = 0; i <= n; i++) {
for(int red = 0; red <= f[n][0]; red++) {
for(int green = 0; green <= f[n][1]; green++) {
for(int cur = 0; cur < 3; cur++) dp[i][red][green][cur] = oo;
}
}
}
dp[0][0][0][0] = 0;
dp[0][0][0][1] = 0;
dp[0][0][0][2] = 0;
for(int i = 0; i < n; i++) {
for(int red = 0; red <= f[n][0]; red++) {
for(int green = 0; green <= f[n][1]; green++) {
for(int cur = 0; cur < 3; cur++) {
if(dp[i][red][green][cur] == oo) continue;
int yellow = i - red - green;
if(yellow < 0) continue;
// swap time
if(i != 0) {
for(int nxt = 0; nxt < 3; nxt++) {
if(nxt == cur) continue;
for(int j = i + 1; j <= n; j++) {
if(convert(a[j]) == nxt) {
int new_red = red + f[j][0] - f[i][0];
int new_green = green + f[j][1] - f[i][1];
int new_yellow = yellow + f[j][2] - f[i][2];
if(new_red <= f[n][0] && new_green <= f[n][1] && new_yellow <= f[n][2]) {
for(int nxt2 = 0; nxt2 < 3; nxt2++) {
if(nxt == nxt2 || f[j][nxt2] - f[i][nxt2] == 0) continue;
mini(dp[j][new_red][new_green][nxt2], dp[i][red][green][cur] + (i + 1 <= j - 1 ? cost[i + 1][j - 1][nxt2]:0) + j - i);
if(j == 3 && new_red == 2 && new_green == 1 && nxt2 == 1) cout<<i<<" "<<cur<<" "<<nxt<<"\n";
}
}
break;
}
}
}
}
for(int j = i + 1; j <= n; j++) {
vector<int> ch;
if(f[j][0] - f[i][0] > 0) ch.pb(0);
if(f[j][1] - f[i][1] > 0) ch.pb(1);
if(f[j][2] - f[i][2] > 0) ch.pb(2);
if(Size(ch) == 3) break;
for(auto nxt:ch) {
int t, l = i + 1, r = j;
if(l % 2 == r % 2) t = nxt;
else {
if(nxt == ch.front()) t = ch.back();
else t = ch.front();
}
if(cur == t) continue;
int new_red = red + f[j][0] - f[i][0];
int new_green = green + f[j][1] - f[i][1];
int new_yellow = yellow + f[j][2] - f[i][2];
if(new_red <= f[n][0] && new_green <= f[n][1] && new_yellow <= f[n][2]) {
mini(dp[j][new_red][new_green][nxt], dp[i][red][green][cur] + cost[i + 1][j][nxt]);
}
}
}
}
}
}
}
int ans = oo;
for(int i = 0; i < 3; i++) mini(ans, dp[n][f[n][0]][f[n][1]][i]);
cout<<(ans == oo ? -1:ans);
}
} sub2;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
sub2.solve();
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In member function 'void sub2::compute(int, int)':
joi2019_ho_t3.cpp:76:13: warning: unused variable 'ans' [-Wunused-variable]
76 | int ans = oo;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
33116 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
33116 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Execution timed out |
871 ms |
781532 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
33116 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
