Submission #930865

#	Time	Username	Problem	Language	Result	Execution time	Memory
930865		Aiperiii	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	196 ms	429516 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=405;
int pref[3][N],dp[3][N][N][N];
vector <int> pos[3];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s='.'+s;
    pos[0].pb(0);pos[1].pb(0);pos[2].pb(0);
    for(int i=1;i<=n;i++){
        if(s[i]=='R'){
            pref[0][i]++;
            pos[0].pb(i);
        }
        else if(s[i]=='G'){
            pref[1][i]++;
            pos[1].pb(i);
        }
        else {
            pref[2][i]++;
            pos[2].pb(i);
        }
        pref[0][i]+=pref[0][i-1];
        pref[1][i]+=pref[1][i-1];
        pref[2][i]+=pref[2][i-1];
        
    }
    for(int i=0;i<pos[0].size();i++){
        for(int j=0;j<pos[1].size();j++){
            for(int k=0;k<pos[2].size();k++){
                for(int l=0;l<3;l++){
                    dp[l][i][j][k]=1e18;
                }
            }
        }
    }
    dp[0][0][0][0]=0;
    dp[1][0][0][0]=0;
    dp[2][0][0][0]=0;
    for(int i=0;i<pos[0].size();i++){
        for(int j=0;j<pos[1].size();j++){
            for(int k=0;k<pos[2].size();k++){
                for(int fr=0;fr<3;fr++){
                    for(int sc=0;sc<3;sc++){
                        if(sc==fr)continue;
                        if(sc==0 && i==pos[0].size()-1)continue;
                        if(sc==1 && j==pos[1].size()-1)continue;
                        if(sc==2 && k==pos[2].size()-1)continue;
                        int pos_fr=0,pos_sc=0,pos_thr=0;
                        int thr=3-fr-sc;
                        if(fr==0)pos_fr=pos[fr][i];
                        else if(fr==1)pos_fr=pos[fr][j];
                        else pos_fr=pos[fr][k];
                        if(thr==0)pos_thr=pos[thr][i];
                        else if(thr==1)pos_thr=pos[thr][j];
                        else pos_thr=pos[thr][k];
                        if(sc==0)pos_sc=pos[sc][i+1];
                        else if(sc==1)pos_sc=pos[sc][j+1];
                        else pos_sc=pos[sc][k+1];
                        int ans=dp[fr][i][j][k];
                        ans+=max(0ll,pref[fr][pos_sc]-pref[fr][pos_fr]);
                        ans+=max(0ll,pref[thr][pos_sc]-pref[thr][pos_thr]);
                        if(sc==0)dp[sc][i+1][j][k]=min(ans,dp[sc][i+1][j][k]);
                        else if(sc==1)dp[sc][i][j+1][k]=min(ans,dp[sc][i][j+1][k]);
                        else dp[sc][i][j][k+1]=min(ans,dp[sc][i][j][k+1]);
                    }
                }
            }
        }
    }
    int ans=1e18;
    for(int i=0;i<3;i++)ans=min(ans,dp[i][pos[0].size()-1][pos[1].size()-1][pos[2].size()-1]);
    if(ans==1e18)ans=-1;
    cout<<ans<<"\n";
}
/*

 */

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<pos[0].size();i++){
      |                 ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j=0;j<pos[1].size();j++){
      |                     ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int k=0;k<pos[2].size();k++){
      |                         ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<pos[0].size();i++){
      |                 ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j=0;j<pos[1].size();j++){
      |                     ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for(int k=0;k<pos[2].size();k++){
      |                         ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                         if(sc==0 && i==pos[0].size()-1)continue;
      |                                     ~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:57:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                         if(sc==1 && j==pos[1].size()-1)continue;
      |                                     ~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                         if(sc==2 && k==pos[2].size()-1)continue;
      |                                     ~^~~~~~~~~~~~~~~~~

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