이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* 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
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);
int n; cin >> n;
string s; cin >> s; s = '1' + s;
vector<int> g[4];
int pref[4][n + 2]; for (int i = 0; i < 3; i++) for (int j = 0; j <= n; j++) pref[i][j] = 0;
int R = 0, G = 1, Y = 2;
int cntr, cntg, cnty;
cntr = cntg = cnty = 0;
pref[1][0] = pref[0][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);
}
컴파일 시 표준 에러 (stderr) 메시지
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:36:13: warning: unused variable 'R' [-Wunused-variable]
36 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp:36:20: warning: unused variable 'G' [-Wunused-variable]
36 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp:36:27: warning: unused variable 'Y' [-Wunused-variable]
36 | int R = 0, G = 1, Y = 2;
| ^
joi2019_ho_t3.cpp: In function 'void fReopen()':
joi2019_ho_t3.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |