Submission #873745

#	Time	Username	Problem	Language	Result	Execution time	Memory
873745		Marco_Escandon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	0 / 100	689 ms	1048576 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    vector<ll> R,G,Y;
    ll n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        char car;
        cin>>car;
        if(car=='R')
            R.push_back(i);
        else if(car=='G')
            G.push_back(i);
        else 
            Y.push_back(i);
    }
    //R.push_back(1e9);
    //G.push_back(1e9);
    //Y.push_back(1e9);
    vector<vector<vector<vector<ll>>>> dp(n+2,vector<vector<vector<ll>>> (R.size()+2,vector<vector<ll>> (G.size()+2,vector<ll>(4,1e15))));
    dp[0][0][0][0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=R.size(); j++)
        {
            for(int k=0; k<=G.size(); k++)
            {
                if(i-j-k-1>=0&&i-j-k<=Y.size())
                    dp[i][j][k][3]=min(min({dp[i-1][j][k][2],dp[i-1][j][k][1],dp[i-1][j][k][0]})+max(0LL,Y[i-j-k-1]-i+1),dp[i][j][k][3]);
                if(j>0)
                    dp[i][j][k][1]=min(min({dp[i-1][j-1][k][2],dp[i-1][j-1][k][3],dp[i-1][j-1][k][0]})+max(0LL,R[j-1]-i+1),dp[i][j][k][1]);
                if(k>0)
                    dp[i][j][k][2]=min(min({dp[i-1][j][k-1][3],dp[i-1][j][k-1][1],dp[i-1][j][k-1][0]})+max(0LL,G[k-1]-i+1),dp[i][j][k][2]);
                //cout<<j<<k<<" "<<dp[i][j][k][1]<<" "<<dp[i][j][k][2]<<" "<<dp[i][j][k][3]<<"\t";
            }
//            cout<<"\n";
        }
        //cout<<"\n\n";
    }
    //cerr<<"asd";
    ll sol=min({dp[n][R.size()][G.size()][1],dp[n][R.size()][G.size()][2],dp[n][R.size()][G.size()][3]});
    if(sol>=1e15)
        sol=-1;
    cout<<sol;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0; j<=R.size(); j++)
      |                      ~^~~~~~~~~~
joi2019_ho_t3.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             for(int k=0; k<=G.size(); k++)
      |                          ~^~~~~~~~~~
joi2019_ho_t3.cpp:30:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if(i-j-k-1>=0&&i-j-k<=Y.size())
      |                                ~~~~~^~~~~~~~~~

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