Submission #928338

#TimeUsernameProblemLanguageResultExecution timeMemory
928338UnforgettableplGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
100 / 100
189 ms794924 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...