/**
* 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;
vector<int> g[4];
int pref[4][n + 2];
int R = 0, G = 1, Y = 2;
int cntr, cntg, cnty;
cntr = cntg = cnty = 0;
pref[0][0] = pref[1][0] = pref[2][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) pref[j][i] += pref[j][i - 1];
if (s[i] == 'R') {
cntr++;
g[0].push_back(i);
pref[0][i]++;
}else if(s[i] == 'G') {
cntg++;
g[2].push_back(i);
pref[2][i]++;
}else if(s[i] == 'Y') {
cnty++;
g[1].push_back(i);
pref[1][i]++;
}
}
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[0][a - 1];
int adj = max(0ll, b - pref[1][j]) + max(0ll, c - pref[2][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[1][b - 1];
int adj = max(0ll, a - pref[0][j]) + max(0ll, c - pref[2][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[2][c - 1];
int adj = max(0ll, b - pref[1][j]) + max(0ll, a - pref[0][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[0][a - 1];
// int cnt = max(0LL, b - pref[{1, pos}]) + max(0LL, c - pref[{2, 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[1][b - 1];
// int cnt = max(0LL, a - pref[{0, pos}]) + max(0LL, c - pref[{2, 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[2][c - 1];
// int cnt = max(0LL, b - pref[{1, pos}]) + max(0LL, a - pref[{0, 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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
600 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
600 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2356 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 12 |
Correct |
1 ms |
860 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2356 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
600 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
