Submission #878951

#	Time	Username	Problem	Language	Result	Execution time	Memory
878951		frostray8653	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	84 ms	3044 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define int long long
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(i, a, b) for (int i = a, I = b; i <= I; i++)
using namespace std;
using pii = pair<int, int>;
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) { cout << a << " "; dbg(b...); }
void ent() { cout << "\n"; }
const int INF = 1e16;
const int N = 405;
int r[N], g[N], y[N];

signed main() {
    IO;

    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> rid, gid, yid;
    rid.push_back(0);
    gid.push_back(0);
    yid.push_back(0);
    FOR(i, 0, n - 1) {
        if (s[i] == 'R')
            r[i] = 1;
        else if (s[i] == 'G')
            g[i] = 1;
        else
            y[i] = 1;
        if (s[i] == 'R')
            rid.push_back(i);
        else if (s[i] == 'G')
            gid.push_back(i);
        else
            yid.push_back(i);
        if (i) {
            r[i] += r[i - 1];
            g[i] += g[i - 1];
            y[i] += y[i - 1];
        }
    }
    int numr = rid.size() - 1, numg = gid.size() - 1, numy = yid.size() - 1;
    // FOR(i, 0, n - 1) dbg(r[i]); ent();
    // FOR(i, 0, n - 1) dbg(g[i]); ent();
    // FOR(i, 0, n - 1) dbg(y[i]); ent();

    vector<vector<int>> dpr(numr + 1, vector<int>(numg + 1, INF));
    vector<vector<int>> dpg(numr + 1, vector<int>(numg + 1, INF));
    vector<vector<int>> dpy(numr + 1, vector<int>(numg + 1, INF));
    dpr[0][0] = dpg[0][0] = dpy[0][0] = 0;

    for (int tot = 1; tot <= n; tot++) {
        vector<vector<int>> ndpr(numr + 1, vector<int>(numg + 1, INF));
        vector<vector<int>> ndpg(numr + 1, vector<int>(numg + 1, INF));
        vector<vector<int>> ndpy(numr + 1, vector<int>(numg + 1, INF));
        for (int i = 0; i <= numr; i++) {
            for (int j = 0; i + j <= tot && j <= numg; j++) {
                int k = tot - i - j;
                if (k > numy) continue;
                if (i)
                    ndpr[i][j] = min(
                        dpg[i - 1][j] + max(0ll, g[gid[j]] - g[rid[i]]) + max(0ll, y[yid[k]] - y[rid[i]]),
                        dpy[i - 1][j] + max(0ll, g[gid[j]] - g[rid[i]]) + max(0ll, y[yid[k]] - y[rid[i]])
                    );
                if (j)
                    ndpg[i][j] = min(
                        dpr[i][j - 1] + max(0ll, r[rid[i]] - r[gid[j]]) + max(0ll, y[yid[k]] - y[gid[j]]),
                        dpy[i][j - 1] + max(0ll, r[rid[i]] - r[gid[j]]) + max(0ll, y[yid[k]] - y[gid[j]])
                    );
                if (k)
                    ndpy[i][j] = min(
                        dpr[i][j] + max(0ll, r[rid[i]] - r[yid[k]]) + max(0ll, g[gid[j]] - g[yid[k]]),
                        dpg[i][j] + max(0ll, r[rid[i]] - r[yid[k]]) + max(0ll, g[gid[j]] - g[yid[k]])
                    );
            }
        }
        swap(dpr, ndpr);
        swap(dpg, ndpg);
        swap(dpy, ndpy);
    }

    int ans = min({dpr[numr][numg], dpg[numr][numg], dpy[numr][numg]});
    if (ans >= INF)
        cout << -1 << "\n";
    else
        cout << ans << "\n";

    return 0;
}

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