Submission #537692

#	Time	Username	Problem	Language	Result	Execution time	Memory
537692		Antekb	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	2 ms	2132 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
const int N=405;
int dp[3][N][N];
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    s='a'+s;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<3; k++){
                if(i||j)dp[k][i][j]=1e9;
            }
        }
    }
    for(int i=1; i<=n; i++){
        int C=0;
        if(s[i]=='Y')C=1;
        if(s[i]=='R')C=2;
        for(int c=0; c<3; c++){
            if(c==C){
                for(int j=1; j<=n; j++){
                    dp[c][i][j]=dp[c][i-1][j-1];
                }
                dp[c][i][1]=dp[c][i-1][0];
            }
            else{
                for(int j=1; j<=n; j++){
                    dp[c][i][j-1]=dp[c][i-1][j]+j-1;
                }
                //dp[c][i][1]=dp[c][i-1][0];
            }
        }
        int m=min({dp[0][i][0], dp[1][i][0], dp[2][i][0]});
        dp[0][i][0]=m;dp[2][i][0]=m;dp[1][i][0]=m;
    }
    /*for(int i=0; i<=n; i++){
        for(int c=0; c<3; c++){
            for(int j=0; j<=n; j++){
                cout<<dp[c][i][j]<<" \n"[j==n];
            }
        }
        cout<<"\n";
    }*/
    if(dp[0][n][0]<1e9)cout<<dp[0][n][0];
    else cout<<"-1";
}

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