Submission #1089063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089063		DeathIsAwe	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	76 ms	185064 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[401][401][401][3], prefix[400][3];
string plants;


int main() {
    int n; cin >> n;
    cin >> plants;
    int rsum = 0, gsum = 0, ysum = 0;
    for (char i: plants) {
        if (i == 'R') {rsum++;}
        if (i == 'G') {gsum++;}
        if (i == 'Y') {ysum++;}
    }
    if (max(max(rsum, gsum), ysum) * 2 > rsum + gsum + ysum + 1) {
        cout << -1; return 0;
    }


    vector<int> rvec, gvec, yvec;
    int rcount = 0, gcount = 0, ycount = 0;
    for (int i=0;i<n;i++) {
        if (plants[i] == 'R') {
            rcount++;
            rvec.push_back(i);
        }
        if (plants[i] == 'G') {
            gcount++;
            gvec.push_back(i);
        }
        if (plants[i] == 'Y') {
            ycount++;
            yvec.push_back(i);
        }
        prefix[i][0] = rcount;
        prefix[i][1] = gcount;
        prefix[i][2] = ycount;
    }


    int rpos, gpos, ypos;
    string curplants;
    for (int i=0;i<rsum+1;i++) {
        for (int j=0;j<gsum+1;j++) {
            for (int k=0;k<ysum+1;k++) {
                if (i == 0 && j == 0 && k == 0) {continue;}
                if (i + j + k == 1) {
                    dp[i][j][k][0] = INT32_MAX; dp[i][j][k][1] = INT32_MAX; dp[i][j][k][2] = INT32_MAX;
                    if (i == 1) {
                        dp[i][j][k][0] = 0;
                    } else  if (j == 1) {
                        dp[i][j][k][1] = 0;
                    } else {
                        dp[i][j][k][2] = 0;
                    }
                    //cout << i << ' ' << j << ' ' << k << ": " << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << ' ' << dp[i][j][k][2] << '\n';
                    continue;
                }


                dp[i][j][k][0] = INT32_MAX; dp[i][j][k][1] = INT32_MAX; dp[i][j][k][2] = INT32_MAX;
                if (i != 0) {
                    rpos = max((ll)0, j - prefix[rvec[i - 1]][1]) + max((ll)0, k - prefix[rvec[i - 1]][2]);
                    if (dp[i - 1][j][k][1] != -1) {
                        dp[i][j][k][0] = min(dp[i][j][k][0], rpos + dp[i - 1][j][k][1]);
                    }
                    if (dp[i - 1][j][k][2] != -1) {
                        dp[i][j][k][0] = min(dp[i][j][k][0], rpos + dp[i - 1][j][k][2]);
                    }
                }
                if (j != 0) {
                    gpos = max((ll)0, i - prefix[gvec[j -1]][0]) + max((ll)0, k - prefix[gvec[j - 1]][2]);
                    if (dp[i][j - 1][k][0] != -1) {
                        dp[i][j][k][1] = min(dp[i][j][k][1], gpos + dp[i][j - 1][k][0]);
                    }
                    if (dp[i][j - 1][k][2] != -1) {
                        dp[i][j][k][1] = min(dp[i][j][k][1], gpos + dp[i][j - 1][k][2]);
                    }
                }
                if (k != 0) {
                    ypos = max((ll)0, j - prefix[yvec[k -1]][1]) + max((ll)0, i - prefix[yvec[k - 1]][0]);
                    if (dp[i][j][k - 1][0] != -1) {
                        dp[i][j][k][2] = min(dp[i][j][k][2], ypos + dp[i][j][k - 1][0]);
                    }
                    if (dp[i][j][k - 1][1] != -1) {
                        dp[i][j][k][2] = min(dp[i][j][k][2], ypos + dp[i][j][k - 1][1]);
                    }
                }
                //cout << i << ' ' << j << ' ' << k << ": " << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << ' ' << dp[i][j][k][2] << '\n';
            }
        }
    }
    

    ll ans = INT32_MAX;
    ans = min(ans, min(dp[rsum][gsum][ysum][0], min(dp[rsum][gsum][ysum][1], dp[rsum][gsum][ysum][2])));
    cout << ans;

}

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