This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 405;
const int oo = 1e9;
vector <int> pos[3];
int dp[N][N][N][4];
int cnt[N][3];
int sz[3];
int n;
template <typename T>
void mini(T &a, T b) {
if (a > b)
a = b;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
char c; cin >> c;
int val = 2;
if (c == 'R')
val = 0;
if (c == 'G')
val = 1;
pos[val].push_back(i);
cnt[i][val]++;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j < 3; j++)
cnt[i][j] += cnt[i - 1][j];
for (int i = 0; i < 3; i++)
sz[i] = pos[i].size();
for (int i = 0; i <= sz[0]; i++)
for (int j = 0; j <= sz[1]; j++)
for (int k = 0; k <= sz[2]; k++)
for (int pre = 0; pre < 3; pre++)
if (i || j || k)
dp[i][j][k][pre] = oo;
for (int i = 0; i <= sz[0]; i++)
for (int j = 0; j <= sz[1]; j++)
for (int k = 0; k <= sz[2]; k++)
for (int pre = 0; pre < 3; pre++) if (dp[i][j][k][pre] < oo) {
int cur = dp[i][j][k][pre];
int x = i + j + k + 1;
if (i < sz[0] && pre != 0) {
int posval = pos[0][i];
if (j > 0)
posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[0][i]][1]);
if (k > 0)
posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[0][i]][2]);
mini(dp[i + 1][j][k][0], cur + posval - x);
}
if (j < sz[1] && pre != 1) {
int posval = pos[1][j];
if (i > 0)
posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[1][j]][0]);
if (k > 0)
posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[1][j]][2]);
mini(dp[i][j + 1][k][1], cur + posval - x);
}
if (k < sz[2] && pre != 2) {
int posval = pos[2][k];
if (j > 0)
posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[2][k]][1]);
if (i > 0)
posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[2][k]][0]);
mini(dp[i][j][k + 1][2], cur + posval - x);
}
}
int ans = oo;
for (int i = 0; i < 3; i++)
ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
if (ans == oo)
ans = -1;
cout << ans;
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... |