oj.uz

Submission #538863

# Submission time Handle Problem Language Result Execution time Memory
538863 2022-03-17T22:56:40 Z Antekb Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 38 ms 9184 KB 
#include<bits/stdc++.h>
using namespace std;
int ans;
string s;

int main(){
    int n;
    cin>>n;
    cin>>s;
    vector<int> V[3];
    for(int i=0; i<n; i++){
        int c=0;
        if(s[i]=='R')c=1;
        if(s[i]=='Y')c=2;
        V[c].push_back(i+1);
    }
    vector<vector<vector<vector<int> > > > dp(3, vector<vector<vector<int> > >(V[0].size()+1
        , vector<vector<int>>(V[1].size()+1, vector<int>(V[2].size()+1, 1e9))));
    dp[0][0][0][0]=dp[1][0][0][0]=dp[2][0][0][0]=0;
    for(int s=1; s<=n; s++){
    for(int i=0; i<=V[0].size(); i++){
        for(int j=0; j<=V[1].size(); j++){
            //for(int k=0; k<=V[2].size(); k++){
                int k=s-i-j;
                if(k<0 || k>V[2].size())continue;
                //if(!k && !i && !j)continue;
                if(i)dp[0][i][j][k]=min(dp[1][i-1][j][k], dp[2][i-1][j][k])+abs(i+j+k-V[0][i-1]);
                if(j)dp[1][i][j][k]=min(dp[0][i][j-1][k], dp[2][i][j-1][k])+abs(i+j+k-V[1][j-1]);
                if(k)dp[2][i][j][k]=min(dp[1][i][j][k-1], dp[0][i][j][k-1])+abs(i+j+k-V[2][k-1]);
            //}
            //cout<<i<<" "<<j<<" "<<k<<" "<<dp[0][i][j][k]<<" "<<dp[1][i][j][k]<<" "<<dp[2][i][j][k]<<"\n";
        }
    }
    }
    int a=V[0].size(), b=V[1].size(), c=V[2].size();
    //cout<<a<<" "<<b<<" "<<c<<" ";
    /*for(int i=0; i<=a; i++){
        for(int j=0; j<=b; j++){
            for(int k=0; k<=b;)
        }
    }*/
    int k=min({dp[0][a][b][c], dp[1][a][b][c], dp[2][a][b][c]});
    if(k>=1e9)cout<<-1;
    else cout<<k/2<<"\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0; i<=V[0].size(); i++){
      |                  ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=0; j<=V[1].size(); j++){
      |                      ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |                 if(k<0 || k>V[2].size())continue;
      |                           ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 37 ms 9128 KB Output is correct
3 Correct 36 ms 9044 KB Output is correct
4 Correct 36 ms 9172 KB Output is correct
5 Correct 38 ms 9172 KB Output is correct
6 Correct 36 ms 9132 KB Output is correct
7 Correct 36 ms 9044 KB Output is correct
8 Correct 35 ms 9136 KB Output is correct
9 Correct 36 ms 9044 KB Output is correct
10 Correct 35 ms 9176 KB Output is correct
11 Correct 35 ms 9132 KB Output is correct
12 Correct 7 ms 2644 KB Output is correct
13 Correct 19 ms 4508 KB Output is correct
14 Correct 22 ms 6272 KB Output is correct
15 Correct 37 ms 9172 KB Output is correct
16 Correct 36 ms 9184 KB Output is correct

Subtask #4
0 / 25.0

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