Submission #630487

#	Time	Username	Problem	Language	Result	Execution time	Memory
630487		colossal_pepe	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	156 ms	163632 KiB

joi2019_ho_t3

#include <iostream>
#include <cstring>
using namespace std;

const int N = 405;
const int INF = N * N;

#define offset(i) (ro[rx][i] + go[gx][i] + yo[yx][i])

int n, rc = 0, gc = 0, yc = 0;
string s;
int ri[N], gi[N], yi[N];
int ro[N][N], go[N][N], yo[N][N];
int dp[N][N][N][3];

void precomp() {
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') {
            ri[rc] = i;
            rc++;
        } else if (s[i] == 'G') {
            gi[gc] = i;
            gc++;
        } else {
            yi[yc] = i;
            yc++;
        }
        for (int j = i - 1; j >= 0; j--) {
            if (s[i] == 'R') ro[rc][j] = 1 + ro[rc - 1][j];
            else if (s[i] == 'G') go[gc][j] = 1 + go[gc - 1][j];
            else yo[yc][j] = 1 + yo[yc - 1][j];
        }
    }
    for (int i = 0; i <= rc; i++) {
        for (int j = 0; j <= gc; j++) {
            for (int k = 0; k <= yc; k++) {
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = -1;
            }
        }
    }
}

int solve(int rx, int gx, int yx, int last) {
    if (rx == rc and gx == gc and yx == yc) return 0;
    if (dp[rx][gx][yx][last] != -1) return dp[rx][gx][yx][last];
    int &ret = dp[rx][gx][yx][last];
    int len = rx + gx + yx;
    int i = ri[rx];
    ret = INF;
    if (last != 0 and rx < rc) ret = min(ret, i + ro[rx][i] + go[gx][i] + yo[yx][i] - len + solve(rx + 1, gx, yx, 0));
    i = gi[gx];
    if (last != 1 and gx < gc) ret = min(ret, i + ro[rx][i] + go[gx][i] + yo[yx][i] - len + solve(rx, gx + 1, yx, 1));
    i = yi[yx];
    if (last != 2 and yx < yc) ret = min(ret, i + ro[rx][i] + go[gx][i] + yo[yx][i] - len + solve(rx, gx, yx + 1, 2));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s;
    precomp();
    int ans = min(solve(0, 0, 0, 0), solve(0, 0, 0, 1));
    cout << (ans >= INF ? -1 : ans) << '\n';
    return 0;
}

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