Submission #647676

#	Time	Username	Problem	Language	Result	Execution time	Memory
647676		Ronin13	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	453 ms	757564 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

int pref[401][3];
int dp[401][401][401][3];

vector <int> vec[3];

int main(){
    int n; cin >> n;
    char c[n + 1];
    for(int i = 1; i <= n;i ++) cin >> c[i];
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++) pref[i][j] = pref[i - 1][j];
        if(c[i] == 'R')
            pref[i][0]++, vec[0].pb(i);
        if(c[i] == 'G')
            pref[i][1]++, vec[1].pb(i);
        if(c[i] == 'Y')
            pref[i][2]++, vec[2].pb(i);
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int x= 0; x <= n; x++){
                for(int k = 0; k < 3; k++){
                    dp[i][j][x][k] = 1e9;
                }
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for(int i = 0; i <= (int)vec[0].size(); i++){
        for(int j = 0; j <= (int)vec[1].size(); j++){
            for(int k = 0; k <= (int)vec[2].size(); k++){
                if(i){
                    int x = vec[0][i - 1];
                    int v = max(pref[x][1] - j, 0);
                    int u = max(pref[x][2] - k, 0);
                    dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + u + v;
                }
                if(j){
                    int x = vec[1][j - 1];
                    int v = max(pref[x][0] - i, 0);
                    int u = max(pref[x][2] - k, 0);
                    dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + u + v;
                }
                if(k){
                    int x = vec[2][k - 1];
                    int v = max(pref[x][0] - i, 0);
                    int u = max(pref[x][1] - j, 0);
                    dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + u + v;
                }
            }
        }
    }
    int l1 = vec[0].size();
    int l2 = vec[1].size();
    int l3 = vec[2].size();
    int x =  min({dp[l1][l2][l3][0], dp[l1][l2][l3][1], dp[l1][l2][l3][2]});
    if(x >= 1e9){
        cout << -1 << "\n";
    }
    else cout << x;
    return 0;
}

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