Submission #1176779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176779		nguyenkhangninh99	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	90 ms	164932 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define int long long

int f[401][401][401][3];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    string s; cin >> s;

    s = ' ' + s;
    int cntr = 0, cntg = 0, cnty = 0, ans = 1e15;
    vector<int> prer(n + 1, 0), preg(n + 1, 0), prey(n + 1, 0);
    vector<int> posr(n + 1, 0), posg(n + 1, 0), posy(n + 1, 0);
    for(int i = 1; i <= n; i++){
        prer[i] = prer[i - 1] + (s[i] == 'R');
        preg[i] = preg[i - 1] + (s[i] == 'G');
        prey[i] = prey[i - 1] + (s[i] == 'Y');
        if(s[i] == 'R') posr[++cntr] = i;
        if(s[i] == 'G') posg[++cntg] = i;
        if(s[i] == 'Y') posy[++cnty] = i;
    }

    for(int r = 0; r <= cntr; r++){
        for(int g = 0; g <= cntg; g++){
            for(int y = 0; y <= cnty; y++){
                for(int k = 0; k < 3; k++) if(r + g + y) f[r][g][y][k] = 1e9 + 5;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int r = 0; r <= cntr; r++){
            for(int g = 0; g <= cntg; g++){
                int y = i - r - g;
                if(y < 0 || y > cnty) continue;
                if(r >= 1) f[r][g][y][0] = min(f[r][g][y][0], min(f[r - 1][g][y][1], f[r - 1][g][y][2]) + posr[r] + max(0ll, g - preg[posr[r]]) + max(0ll, y - prey[posr[r]]) - i);
                if(g >= 1) f[r][g][y][1] = min(f[r][g][y][1], min(f[r][g - 1][y][0], f[r][g - 1][y][2]) + posg[g] + max(0ll, r - prer[posg[g]]) + max(0ll, y - prey[posg[g]]) - i);
                if(y >= 1) f[r][g][y][2] = min(f[r][g][y][2], min(f[r][g][y - 1][0], f[r][g][y - 1][1]) + posy[y] + max(0ll, r - prer[posy[y]]) + max(0ll, g - preg[posy[y]]) - i);
            }
        }
    }

    for(int k = 0; k < 3; k++) ans = min(ans, f[cntr][cntg][cnty][k]);
    cout << (ans > 1e8 ? -1 : ans);
}

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