Submission #559933

#	Time	Username	Problem	Language	Result	Execution time	Memory
559933		Notred132	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	485 ms	769880 KiB

joi2019_ho_t3

#include <iostream>

using namespace std;
const int maxn = 405;
int n;
char a[maxn];
int f[maxn][3][maxn][maxn];
int x[3][maxn];
int cnt[3];
int g[3][maxn][3];

int main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        if(a[i] == 'R') {
            x[0][++cnt[0]] = i;
            g[0][cnt[0]][1] = cnt[1];
            g[0][cnt[0]][2] = cnt[2];
        }
        else if(a[i] == 'G') {
            x[1][++cnt[1]] = i;
            g[1][cnt[1]][0] = cnt[0];
            g[1][cnt[1]][2] = cnt[2];
        }
        else {
            x[2][++cnt[2]] = i;
            g[2][cnt[2]][0] = cnt[0];
            g[2][cnt[2]][1] = cnt[1];
        }
    }
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= 2; ++j) {
            for(int p = 0; p <= n; ++p) {
                for(int q = 0; q <= n; ++q) f[i][j][p][q] = 1e9;
            }
        }
    }
    for(int i = 0; i <= 2; ++i) {
        if(cnt[i] == 0) continue;
        f[1][i][0][0] = x[i][1] - 1;
    }
    for(int i = 2; i <= n; ++i) {
        for(int j = 0; j <= 2; ++j) {
            for(int p = 0; p <= i - 1; ++p) {
                for(int q = 0; q + p <= i - 1; ++q) {
                    int j1 = 0;
                    int j2 = 1;
                    if(j == 0) {j1 = 1; j2 = 2;}
                    else if(j == 1) j2 = 2;
                    if(p > cnt[j1]) continue;
                    if(q > cnt[j2]) continue;
                    int tmp = i - p - q;
                    if(tmp > cnt[j]) continue;
                    int g1 = g[j][tmp][j1];
                    int g2 = g[j][tmp][j2];
                    if(j < j2) f[i][j][p][q] = min(f[i][j][p][q], f[i - 1][j1][tmp - 1][q] + max(0, g1 - p) + max(0, g2 - q));
                    else f[i][j][p][q] = min(f[i][j][p][q], f[i - 1][j1][q][tmp - 1] + max(0, g1 - p) + max(0, g2 - q));
                    if(j < j1) f[i][j][p][q] = min(f[i][j][p][q], f[i - 1][j2][tmp - 1][p] + max(0, g1 - p) + max(0, g2 - q));
                    else f[i][j][p][q] = min(f[i][j][p][q], f[i - 1][j2][p][tmp - 1] + max(0, g1 - p) + max(0, g2 - q));
                }
            }
        }
    }
    int res = min(f[n][2][cnt[0]][cnt[1]], min(f[n][0][cnt[1]][cnt[2]], f[n][1][cnt[0]][cnt[2]]));
    if(res == 1e9) cout << -1;
    else cout << res;
    return 0;
}

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