Submission #212499

#	Time	Username	Problem	Language	Result	Execution time	Memory
212499		PeppaPig	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	105 ms	194312 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define iii tuple<int, int, int>

using namespace std;

const int N = 405;

int n;
int cnt[3], dp[3][N][N][N];
char A[N];
vector<iii> vec[3];

int f(char c) {
    if(c == 'R') return 0;
    if(c == 'G') return 1;
    return 2;
}

int cost(int c, iii a, iii b) {
    int ret = 0;
    if(c != 0) ret += max(0, get<0>(b) - get<0>(a));
    if(c != 1) ret += max(0, get<1>(b) - get<1>(a));
    if(c != 2) ret += max(0, get<2>(b) - get<2>(a));
    return ret;
}

int main() {
    scanf("%d %s", &n, A + 1);
    for(int i = 1; i <= n; i++) {
        ++cnt[f(A[i])]; 
        vec[f(A[i])].emplace_back(cnt[0], cnt[1], cnt[2]);
    }

    int R = cnt[0], G = cnt[1], Y = cnt[2];
    for(int i = 0; i <= R; i++) for(int j = 0; j <= G; j++) for(int k = 0; k <= Y; k++) {
        if(!i && !j && !k) continue;
        dp[0][i][j][k] = dp[1][i][j][k] = dp[2][i][j][k] = 1e9;
        if(i) dp[0][i][j][k] = min(dp[1][i-1][j][k], dp[2][i-1][j][k]) + cost(0, vec[0][i-1], {i, j, k});
        if(j) dp[1][i][j][k] = min(dp[0][i][j-1][k], dp[2][i][j-1][k]) + cost(1, vec[1][j-1], {i, j, k});
        if(k) dp[2][i][j][k] = min(dp[0][i][j][k-1], dp[1][i][j][k-1]) + cost(2, vec[2][k-1], {i, j, k});
    }
    int ans = 1e9;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[i][R][G][Y]);
    if(ans == 1e9) printf("-1\n");
    else printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %s", &n, A + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

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