Submission #1114276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114276		Icelast	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	143 ms	196680 KiB

joi2019_ho_t3

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
int f[401][401][401][3];
void solve(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    s = ' ' + s;
    int R = 0, G = 0, Y = 0;
    vector<int> pfr(n+1, 0), pfg(n+1, 0), pfy(n+1, 0);
    vector<int> pr(n+1, 0), pg(n+1, 0), py(n+1, 0);
    for(int i = 1; i <= n; i++){
        pfr[i] = pfr[i-1];
        pfg[i] = pfg[i-1];
        pfy[i] = pfy[i-1];
        if(s[i] == 'R'){
            R++;
            pr[R] = i;
            pfr[i]++;
        }
        if(s[i] == 'G'){
            G++;
            pg[G] = i;
            pfg[i]++;
        }
        if(s[i] == 'Y'){
            Y++;
            py[Y] = i;
            pfy[i]++;
        }
    }
    auto chmin = [&](int &a, int b) -> void{
        a = min(a, b);
    };
    for(int r = 0; r <= R; r++){
        for(int g = 0; g <= G; g++){
            for(int y = 0; y <= Y; y++){
                for(int k = 0; k < 3; k++){
                    f[r][g][y][k] = INF;
                }
            }
        }
    }
    for(int k = 0; k < 3; k++){
        f[0][0][0][k] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int r = 0; r <= R; r++){
            for(int g = 0; g <= G; g++){
                int y = i-r-g;
                if(y < 0 || y > Y) continue;
                if(r > 0){
                    chmin(f[r][g][y][0], min(f[r-1][g][y][1], f[r-1][g][y][2]) + pr[r]+max(0, g-pfg[pr[r]]) + max(0, y-pfy[pr[r]])-i);
                }
                if(g > 0){
                    chmin(f[r][g][y][1], min(f[r][g-1][y][0], f[r][g-1][y][2]) + pg[g]+max(0, r-pfr[pg[g]]) + max(0, y-pfy[pg[g]])-i);
                }
                if(y > 0){
                    chmin(f[r][g][y][2], min(f[r][g][y-1][0], f[r][g][y-1][1]) + py[y]+max(0, r-pfr[py[y]]) + max(0, g-pfg[py[y]])-i);
                }
            }
        }
    }
    int ans = INF;
    for(int k = 0; k < 3; k++){
        chmin(ans, f[R][G][Y][k]);
    }
    if(ans > 1e8) ans = -1;
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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