제출 #965035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965035		Alihan_8	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	267 ms	254036 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e9 + 1;

const int N = 201;

int dp[N * 2][N][N][4];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    string s; cin >> s;
    s = '#' + s;
    map <char,int> id;
    id['R'] = 0, id['G'] = 1, id['Y'] = 2;
    vector <ar<int,3>> pf(n + 1);
    for ( int i = 1; i <= n; i++ ){
        pf[i] = pf[i - 1];
        pf[i][id[s[i]]]++;
    }
    { // modifying
        int it = 0;
        for ( int j = 1; j <= 2; j++ ){
            if ( pf[n][j] >= pf[n][it] ){
                it = j;
            }
        }
        for ( int j = 0; j <= n; j++ ){
            swap(pf[j][it], pf[j][2]);
        }
    }
    vector <vector<int>> pos(3, vector <int> (n + 2, -1));
    for ( int i = 0; i < 3; i++ ){
        for ( int j = 0; j <= n; j++ ){
            int l = 0, r = n;
            while ( l < r ){
                int md = (l + r) >> 1;
                if ( pf[md][i] < j ){
                    l = md + 1;
                } else r = md;
            }
            if ( pf[l][i] >= j ){
                pos[i][j] = l;
            }
        }
    }
    for ( int i = 0; i <= n; i++ ){
        for ( int j = 0; j <= pf[n][0]; j++ ){
            for ( int k = 0; k <= pf[n][1]; k++ ){
                for ( int lst = 0; lst <= 3; lst++ ){
                    dp[i][j][k][lst] = inf;
                }
            }
        }
    }
    dp[0][0][0][3] = 0;
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j <= pf[n][0]; j++ ){
            for ( int k = 0; k <= pf[n][1]; k++ ){
                for ( int lst = 0; lst < 3 + !i; lst++ ){
                    int &tmp = dp[i][j][k][lst];
                    if ( tmp == inf ){
                        continue;
                    }
                    int p = i - (j + k);
                    vector <int> a(3), t = {j, k, p};
                    for ( int it = 0; it < 3; it++ ){
                        int l = pos[it][t[it] + 1];
                        if ( l == -1 ){
                            a[it] = -1;
                        } else{
                            for ( int q = 0; q < 3; q++ ){
                                if ( q != it ){
                                    a[it] += max(0, pf[l][q] - t[q]);
                                }
                            }
                        }
                    }
                    if ( a[0] != -1 && lst != 0 ){
                        chmin(dp[i + 1][j + 1][k][0], tmp + a[0]);
                    }
                    if ( a[1] != -1 && lst != 1 ){
                        chmin(dp[i + 1][j][k + 1][1], tmp + a[1]);
                    }
                    if ( a[2] != -1 && lst != 2 ){
                        chmin(dp[i + 1][j][k][2], tmp + a[2]);
                    }
                }
            }
        }
    }
    int opt = inf;
    for ( int i = 0; i < 3; i++ ){
        chmin(opt, dp[n][pf[n][0]][pf[n][1]][i]);
    }
    if ( opt == inf ){
        opt = -1;
    }
    cout << opt;

    cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25