oj.uz

Submission #873728

# Submission time Handle Problem Language Result Execution time Memory
873728 2023-11-15T14:36:30 Z Marco_Escandon Growing Vegetable is Fun 3 (JOI19_ho_t3) C++11
0 / 100
 500 ms 1048576 KB 
#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,1e9))));
    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()][0],dp[n][R.size()][G.size()][1],dp[n][R.size()][G.size()][2],dp[n][R.size()][G.size()][3]});
    if(sol>=1e9)
        sol=-1;
    cout<<sol;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 436 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 609 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 436 KB Output isn't correct
12 Halted 0 ms 0 KB -