Submission #676426

#	Time	Username	Problem	Language	Result	Execution time	Memory
676426		stevancv	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	170 ms	133656 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 1e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> a[3], b[3][3];
    int X, Y, Z;
    X = Y = Z = 1;
    for (int l = 0; l < 3; l++) a[l].push_back(-1);
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) b[i][j].push_back(-1);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') {
            a[0].push_back(i);
            X += 1;
            b[0][1].push_back(Y);
            b[0][2].push_back(Z);
        }
        if (s[i] == 'G') {
            a[1].push_back(i);
            Y += 1;
            b[1][0].push_back(X);
            b[1][2].push_back(Z);
        }
        if (s[i] == 'Y') {
            a[2].push_back(i);
            Z += 1;
            b[2][0].push_back(X);
            b[2][1].push_back(Y);
        }
    }
    vector<vector<vector<vector<int>>>> dp(X);
    for (int i = 0; i < X; i++) {
        dp[i].resize(Y);
        for (int j = 0; j < Y; j++) {
            dp[i][j].resize(Z, vector<int>(3, inf));
        }
    }
    for (int l = 0; l < 3; l++) dp[0][0][0][l] = 0;
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < Z; k++) {
                int pos = i + j + k - 1;
                if (i > 0) dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + a[0][i] - pos + max(0, j - b[0][1][i] + 1) + max(0, k - b[0][2][i] + 1);
                if (j > 0) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + a[1][j] - pos + max(0, i - b[1][0][j] + 1) + max(0, k - b[1][2][j] + 1);
                if (k > 0) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + a[2][k] - pos + max(0, i - b[2][0][k] + 1) + max(0, j - b[2][1][k] + 1);
            }
        }
    }
    int ans = inf;
    for (int l = 0; l < 3; l++) smin(ans, dp[X - 1][Y - 1][Z - 1][l]);
    if (ans == inf) ans = -1;
    cout << ans << en;
    return 0;
}

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