Submission #928338

#	Time	Username	Problem	Language	Result	Execution time	Memory
928338		Unforgettablepl	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	189 ms	794924 KiB

joi2019_ho_t3

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

#define int long long

const int INF = 1e15;

int pref[3][401][401];
int DP[401][401][401][3];
int idx[3][401];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int red = 0;
    int green = 0;
    int yellow = 0;
    for (int i = 1; i <= n; i ++) {
        char a;cin>>a;
        if(a=='R'){
            idx[0][++red]=i;
            for(int j=1;j<=n;j++)pref[0][red][j]=pref[0][red-1][j];
            for(int j=i;j<=n;j++)pref[0][red][j]++;
        } else if(a=='G'){
            idx[1][++green]=i;
            for(int j=1;j<=n;j++)pref[1][green][j]=pref[1][green-1][j];
            for(int j=i;j<=n;j++)pref[1][green][j]++;
        } else {
            idx[2][++yellow]=i;
            for(int j=1;j<=n;j++)pref[2][yellow][j]=pref[2][yellow-1][j];
            for(int j=i;j<=n;j++)pref[2][yellow][j]++;
        }
    }
    for(int i=0;i<=red;i++){
        for(int j=0;j<=green;j++){
            for(int k=0;k<=yellow;k++){
                if(i==0 and j==0 and k==0)continue;
                // If last is red
                if(i==0)DP[i][j][k][0]=INF;
                else {
                    DP[i][j][k][0]=min(DP[i-1][j][k][1],DP[i-1][j][k][2])+idx[0][i]-1-pref[0][i][idx[0][i]-1]-pref[1][j][idx[0][i]-1]-pref[2][k][idx[0][i]-1];
                }
                // If last is green
                if(j==0)DP[i][j][k][1]=INF;
                else {
                    DP[i][j][k][1]=min(DP[i][j-1][k][0],DP[i][j-1][k][2])+idx[1][j]-1-pref[0][i][idx[1][j]-1]-pref[1][j][idx[1][j]-1]-pref[2][k][idx[1][j]-1];
                }
                // If last is yellow
                if(k==0)DP[i][j][k][2]=INF;
                else {
                    DP[i][j][k][2]=min(DP[i][j][k-1][0],DP[i][j][k-1][1])+idx[2][k]-1-pref[0][i][idx[2][k]-1]-pref[1][j][idx[2][k]-1]-pref[2][k][idx[2][k]-1];
                }
            }
        }
    }
    int ans = min({DP[red][green][yellow][0],DP[red][green][yellow][1],DP[red][green][yellow][2]});
    cout << (ans>=INF ? -1 : ans) << '\n';
}

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