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>
using namespace std;
const int DIM = 405;
int dp[DIM][DIM][DIM][3], idx[3];
int tot[3], psm[DIM][3], lst[DIM][3];
inline int f(int &x, int y) {
x = min(x, y); }
int main(void) {
#ifdef HOME
freopen("vegetables.in", "r", stdin);
freopen("vegetables.out", "w", stdout);
#endif
int n; cin >> n;
for (int i = 1; i <= n; ++i) {
char ch; cin >> ch;
if (ch == 'R') { lst[++tot[0]][0] = i; ++psm[i][0]; }
if (ch == 'G') { lst[++tot[1]][1] = i; ++psm[i][1]; }
if (ch == 'Y') { lst[++tot[2]][2] = i; ++psm[i][2]; }
for (int l = 0; l <= 2; ++l) {
psm[i][l] += psm[i - 1][l]; } }
memset(dp, 0x3f, sizeof dp);
for (int l = 0; l <= 2; ++l) {
dp[0][0][0][l] = 0; }
for (idx[0] = 0; idx[0] <= tot[0]; ++idx[0]) {
for (idx[1] = 0; idx[1] <= tot[1]; ++idx[1]) {
for (idx[2] = 0; idx[2] <= tot[2]; ++idx[2]) {
for (int ls = 0; ls <= 2; ++ls) {
for (int cr = 0; cr <= 2; ++cr) {
if (ls != cr and idx[cr] < tot[cr]) {
int cst = 0;
for (int p = 0; p <= 2; ++p) { if (p != cr) {
cst += max(0, psm[lst[idx[cr] + 1][cr]][p] - idx[p]); } }
f(dp[idx[0] + (cr == 0)][idx[1] + (cr == 1)][idx[2] + (cr == 2)][cr], dp[idx[0]][idx[1]][idx[2]][ls] + cst); } } } } } }
int v = min( { dp[tot[0]][tot[1]][tot[2]][0], dp[tot[0]][tot[1]][tot[2]][1], dp[tot[0]][tot[1]][tot[2]][2] } );
cout << (v >= DIM * DIM ? -1 : v) << endl;
return 0; }
Compilation message (stderr)
joi2019_ho_t3.cpp: In function 'int f(int&, int)':
joi2019_ho_t3.cpp:10:17: warning: no return statement in function returning non-void [-Wreturn-type]
x = min(x, y); }
^
# | 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... |