제출 #1333900

#제출 시각아이디문제언어결과실행 시간메모리
1333900retardeGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
60 / 100
493 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

int n; string s;
const int mxn = 401;
int dp[mxn][mxn][mxn][3];
int rp[mxn], gp[mxn], yp[mxn];

// R, G, Y
// 0, 1, 2

int cnt(int id, int y) {
    // cnt < y
    // if (!x.size()) return 0;
    // if (x[x.size() - 1] < y) return x.size();
    // auto it = lower_bound(all(x), y);
    // if (*it < y) return x.size();
    // if (it - x.begin() != 0) {
    //     return (it - x.begin());
    // } else {
    //     return 0;
    // }

    if (y == 0) return 0;

    if (id == 0) return rp[y - 1];
    else if (id == 1) return gp[y - 1];
    else return yp[y - 1];
}

void cmn(int &x, int y) {x = min(x, y);}

void pre() {
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) for (int l = 0; l < 3; l++) dp[i][j][k][l] = 1e18;
    
    if (s[0] == 'R') rp[0]++;
    else if (s[0] == 'G') gp[0]++;
    else yp[0]++;

    for (int i = 1; i < n; i++) {
        rp[i] = rp[i - 1] += (s[i] == 'R');
        gp[i] = gp[i - 1] += (s[i] == 'G');
        yp[i] = yp[i - 1] += (s[i] == 'Y');
    }
}

inline void solve() {
    cin >> n >> s; pre();
    vi r, g, y; for (int i = 0; i < n; i++) {
        if (s[i] == 'R') r.pb(i);
        else if (s[i] == 'G') g.pb(i);
        else y.pb(i);
    }
    if (r.size()) dp[1][0][0][0] = r[0];
    if (g.size()) dp[0][1][0][1] = g[0];
    if (y.size()) dp[0][0][1][2] = y[0];

    for (int rc = 0; rc <= r.size(); rc++) {
        for (int gc = 0; gc <= g.size(); gc++) {
            for (int yc = 0; yc <= y.size(); yc++) {
                if (rc + gc + yc <= 1) continue;

                bool d = false;
                if (rc == 1 && gc == 0 && yc == 1) {
                    d = true;
                }

                // R is last
                if (rc) {
                    int pos = r[rc - 1];
                    int mv = pos - min(gc, cnt(1, pos)) - min(yc, cnt(2, pos)) - (rc - 1);
                    // if (d) cout << "RLAST " << r[rc - 1] << " - " << (rc - 1) << " - " << cnt(g, pos) << " - " << cnt(y, pos) << '\n';
                    cmn(dp[rc][gc][yc][0], dp[rc - 1][gc][yc][1] + mv);
                    cmn(dp[rc][gc][yc][0], dp[rc - 1][gc][yc][2] + mv);
                }

                // G is last
                if (gc) {
                    int pos = g[gc - 1];
                    int mv = pos - min(rc, cnt(0, pos)) - min(yc, cnt(2, pos)) - (gc - 1);
                    // if (d) cout << "GLAST " << mv << '\n';
                    cmn(dp[rc][gc][yc][1], dp[rc][gc - 1][yc][0] + mv);
                    cmn(dp[rc][gc][yc][1], dp[rc][gc - 1][yc][2] + mv);
                }

                // Y is last
                if (yc) {
                    int pos = y[yc - 1];
                    int mv = pos - min(rc, cnt(0, pos)) - min(gc, cnt(1, pos)) - (yc - 1);
                    // if (d) cout << "YLAST " << y[yc - 1] << " - " << (yc - 1) << " - " << cnt(r, pos) << " - " << cnt(g, pos) << '\n';
                    cmn(dp[rc][gc][yc][2], dp[rc][gc][yc - 1][0] + mv);
                    cmn(dp[rc][gc][yc][2], dp[rc][gc][yc - 1][1] + mv);
                }
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         for (int k = 0; k < n; k++) {
    //             for (int l = 0; l < 3; l++) {
    //                 cout << "DP " << i << " " << j << " " << k << " last " << "RGY"[l] << ": " << dp[i][j][k][l] << '\n';
    //             }
    //         }
    //     }
    // }

    int ans = min(dp[r.size()][g.size()][y.size()][0], min(dp[r.size()][g.size()][y.size()][1], dp[r.size()][g.size()][y.size()][2]));
    cout << (ans == 1e18 ? -1 : ans) << '\n';
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:142:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:143:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...