/**
* data : 09.07.2024
*
**/
#include <bits/stdc++.h>
// #include "algo/turnikmen.h"
using namespace std;
#define int long long
#define bitt __builtin_popcountll
#define bitzero __builtin_clz
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
// #pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
// #pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
// #pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC target("avx")
void fReopen () {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
signed main (/* time : 9:17 AM */) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fReopen();
int n; cin >> n;
string s; cin >> s; s = '1' + s;
map<char, vector<int>> g;
map<pair<char, int>, int> pref;
int R = 0, G = 1, Y = 2;
int cntr, cntg, cnty;
cntr = cntg = cnty = 0;
for (int i = 1; i <= n; i++) {
g[s[i]].push_back(i);
pref[{'Y', i}] = pref[{'Y', i - 1}];
pref[{'G', i}] = pref[{'G', i - 1}];
pref[{'R', i}] = pref[{'R', i - 1}];
pref[{s[i], i}] += 1;
cntr += s[i] == 'R';
cnty += s[i] == 'Y';
cntg += s[i] == 'G';
}
int dp[n + 1][cntr + 1][cnty + 1][3] = { };
for (int i = 1; i <= n; i++) {
for (int a = 0; a <= cntr; a++) {
for (int b = 0; b <= cnty; b++) {
for (int j = 0; j < 3; j++)
dp[i][a][b][j] = 1e18;
}
}
}
for (int i = 0; i < 3; i++) dp[0][0][0][i] = 0;
for (int i = 1; i <= n; i++) {
for (int a = 0; a <= cntr; a++) {
for (int b = 0; b <= cnty; b++) {
if (a + b > i) continue;
int c = i - a - b;
if (c > cntg) continue;
for (int last = 0; last < 3; last++) {
if (last != 0 && a) {
int j = g['R'][a - 1];
int adj = max(0ll, b - pref[{'Y', j}]) + max(0ll, c - pref[{'G', j}]);
int val = max(0ll, j + adj - i);
dp[i][a][b][0] = min(dp[i][a][b][0], dp[i - 1][a - 1][b][last] + val);
}
if (last != 1 && b) {
int j = g['Y'][b - 1];
int adj = max(0ll, a - pref[{'R', j}]) + max(0ll, c - pref[{'G', j}]);
int val = max(0ll, j + adj - i);
dp[i][a][b][1] = min(dp[i][a][b][1], dp[i - 1][a][b - 1][last] + val);
}
if (last != 2 && c) {
int j = g['G'][c - 1];
int adj = max(0ll, a - pref[{'R', j}]) + max(0ll, b - pref[{'Y', j}]);
int val = max(0ll, j + adj - i);
dp[i][a][b][2] = min(dp[i][a][b][2], dp[i - 1][a][b][last] + val);
}
}
// if (a > 0) {
// int pos = g['R'][a - 1];
// int cnt = max(0LL, b - pref[{'Y', pos}]) + max(0LL, c - pref[{'G', pos}]);
// dp[i][a][b][0] = min(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 > 0) {
// int pos = g['Y'][b - 1];
// int cnt = max(0LL, a - pref[{'R', pos}]) + max(0LL, c - pref[{'G', pos}]);
// dp[i][a][b][1] = min(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 > 0) {
// int pos = g['G'][c - 1];
// int cnt = max(0LL, b - pref[{'Y', pos}]) + max(0LL, a - pref[{'R', pos}]);
// dp[i][a][b][2] = min(dp[i][a][b][2], min(dp[i - 1][a][b][0], dp[i - 1][a][b][1]) + max(0LL, pos + cnt - i));
// }
}
}
}
// for (int i = 1; i <= n; i++) {
// for (int a = 0; a <= cntr; a++) {
// for (int b = 0; b <= cnty; b++) {
// if (a + b > i) continue;
// int c = i - a - b;
// if (c > cntg) continue;
// cout << dp[i][]
// }
// }
// }
int res = min({dp[n][cntr][cnty][0], dp[n][cntr][cnty][1], dp[n][cntr][cnty][2]});
cout << (res == 1e18 ? -1 : res);
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:77:13: warning: unused variable 'R' [-Wunused-variable]
77 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp:77:20: warning: unused variable 'G' [-Wunused-variable]
77 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp:77:27: warning: unused variable 'Y' [-Wunused-variable]
77 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp: In function 'void fReopen()':
joi2019_ho_t3.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
2908 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
2908 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
9 ms |
3932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
2908 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
