Submission #676407

#	Time	Username	Problem	Language	Result	Execution time	Memory
676407		stevancv	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	8 ms	3816 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> x, y, z;
    x.push_back(-1);
    y.push_back(-1);
    z.push_back(-1);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') x.push_back(i);
        if (s[i] == 'G') y.push_back(i);
        if (s[i] == 'Y') z.push_back(i);
    }
    int X = x.size();
    int Y = y.size();
    int Z = z.size();
    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]) + max(0, x[i] - pos);
                if (j > 0) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + max(0, y[j] - pos);
                if (k > 0) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + max(0, z[k] - pos);
            }
        }
    }
    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: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25