Submission #962461

#	Time	Username	Problem	Language	Result	Execution time	Memory
962461		peterandvoi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	180 ms	135504 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 405, INF = (int) 1e9;

int n;
char s[N];
int a[N], sz[N];
int cost[3][N][N];
vector<int> pos[3];

template<class A, class B>
bool mini(A &a, const B &b) {
    return a > b ? a = b, true : false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        a[i] = (s[i] == 'Y' ? 2 : (s[i] == 'G'));
        pos[a[i]].emplace_back(i);
        sz[a[i]]++;
    }
    for (int c = 0; c < 3; ++c) {
        for (int i = 0; i <= sz[c]; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = i; k < sz[c]; ++k) {
                    cost[c][i][j] += j > pos[c][k];
                }
            }
        }
    }
    vector<vector<vector<vector<int>>>> dp(sz[0] + 1, vector<vector<vector<int>>>(sz[1] + 1, vector<vector<int>>(sz[2] + 1, vector<int>(3, INF))));
    for (int c = 0; c < 3; ++c) {
        dp[0][0][0][c] = 0;
    }
    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 c = 0; c < 3; ++c) {
                    if (dp[i][j][k][c] != INF) {
                        auto calc = [&](int idx) {
                            return cost[0][i][idx] + cost[1][j][idx] + cost[2][k][idx];
                        };
                        if (c != 0 && i + 1 <= sz[0]) {
                            mini(dp[i + 1][j][k][0], dp[i][j][k][c] + calc(pos[0][i]));
                        }
                        if (c != 1 && j + 1 <= sz[1]) {
                            mini(dp[i][j + 1][k][1], dp[i][j][k][c] + calc(pos[1][j]));
                        }
                        if (c != 2 && k + 1 <= sz[2]) {
                            mini(dp[i][j][k + 1][2], dp[i][j][k][c] + calc(pos[2][k]));
                        }
                    }
                }
            }
        }
    }
    int res = INF;
    for (int c = 0; c < 3; ++c) {
        res = min(res, dp[sz[0]][sz[1]][sz[2]][c]);
    }
    cout << (res == INF ? -1 : res);
}

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