Submission #1139493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139493		VMaksimoski008	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	309 ms	165000 KiB

joi2019_ho_t3

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

ll dp[405][405][405][3];

signed main() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> a(n+1), vec[3];

    for(int i=0; i<n; i++) {
        int val = 0;
        if(s[i] == 'G') val = 1;
        if(s[i] == 'Y') val = 2;
        a[i+1] = val;
        vec[val].push_back(i+1);
    }

    vector<int> sz(3);
    for(int i=0; i<3; i++) sz[i] = vec[i].size();
    for(int i=0; i<=sz[0]; i++)
        for(int j=0; j<=sz[1]; j++)
            for(int k=0; k<=sz[2]; k++)
                for(int x=0; x<3; x++) dp[i][j][k][x] = 1e18;
    for(int i=0; i<3; i++) dp[0][0][0][i] = 0;

    vector<int> it(3);
    for(it[0]=0; it[0]<=sz[0]; it[0]++) {
        for(it[1]=0; it[1]<=sz[1]; it[1]++) {
            for(it[2]=0; it[2]<=sz[2]; it[2]++) {
                for(int x=0; x<3; x++) {
                    if(!it[x]) continue;
                    int p = vec[x][it[x]-1];
                    ll cost = 0;
                        
                    for(int y=0; y<3; y++) {
                        if(x == y) continue;
                        cost += max(0, int(lower_bound(vec[y].begin(), vec[y].end(), p) - vec[y].begin()) - it[y]);
                    }

                    vector<int> it2 = it; it2[x]--;
                    for(int lst=0; lst<3; lst++)
                     if(lst != x) dp[it[0]][it[1]][it[2]][x] = min(dp[it[0]][it[1]][it[2]][x], dp[it2[0]][it2[1]][it2[2]][lst] + cost);
                }
            }
        }
    }

    ll ans = 1e18;
    for(int i=0; i<3; i++) ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
    cout << (ans < 1e18 ? ans : -1) << '\n';
}

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