oj.uz

Submission #738445

# Submission time Handle Problem Language Result Execution time Memory
738445 2023-05-08T19:01:39 Z Ahmed57 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 252 ms 640824 KB 
#include <bits/stdc++.h>

using namespace std;
long long dp[3][301][301][301];
vector<int>col[3];
long long pref[3][401];
long long solve(int la,int r,int g,int b){
    if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
        return 0;
    }
    if(dp[la][r][g][b]!=-1)return dp[la][r][g][b];
    long long c1 = 1e18;
    for(int ne = 0;ne<3;ne++){
        if(ne==la)continue;
        if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
        int p1 = 0 , p2 = 0 , p3 = 0 , dif;
        if(ne==0)p1 = col[ne][r+1];
        if(ne==1)p1 = col[ne][g+1];
        if(ne==2)p1 = col[ne][b+1];
        if(la==0)p2 = col[la][r];
        if(la==1)p2 = col[la][g];
        if(la==2)p2 = col[la][b];
        if(ne!=0&&la!=0){p3 = col[0][r];dif = 0;}
        if(ne!=1&&la!=1){p3 = col[1][g];dif = 1;}
        if(ne!=2&&la!=2){p3 = col[2][b];dif = 2;}
        long long ans = max(0LL,pref[la][p1]-pref[la][p2])+max(0LL,pref[dif][p1]-pref[dif][p3]);
        if(ne==0)c1 = min(c1,solve(ne,r+1,g,b)+ans);
        if(ne==1)c1 = min(c1,solve(ne,r,g+1,b)+ans);
        if(ne==2)c1 = min(c1,solve(ne,r,g,b+1)+ans);
    }
    return dp[la][r][g][b] =c1;
}
signed main(){
    int len;cin>>len;
    string s;cin>>s;
    s = 'a'+s;
    col[0].push_back(0);col[1].push_back(0);col[2].push_back(0);
    memset(pref,0,sizeof pref);
    for(int i = 1;i<s.size();i++){
        pref[0][i]+=pref[0][i-1];
        pref[1][i]+=pref[1][i-1];
        pref[2][i]+=pref[2][i-1];
        if(s[i]=='R'){col[0].push_back(i);pref[0][i]++;}
        if(s[i]=='G'){col[1].push_back(i);pref[1][i]++;}
        if(s[i]=='Y'){col[2].push_back(i);pref[2][i]++;}
    }
    memset(dp,-1,sizeof dp);
    cout<<min({solve(0,0,0,0),solve(1,0,0,0),solve(2,0,0,0)});
}

Compilation message

joi2019_ho_t3.cpp: In function 'long long int solve(int, int, int, int)':
joi2019_ho_t3.cpp:8:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
      |        ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
      |                            ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:8:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
      |                                                ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
      |                    ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
      |                                                 ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:81: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
      |                                                                              ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 1;i<s.size();i++){
      |                   ~^~~~~~~~~
joi2019_ho_t3.cpp: In function 'long long int solve(int, int, int, int)':
joi2019_ho_t3.cpp:26:94: warning: 'dif' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |         long long ans = max(0LL,pref[la][p1]-pref[la][p2])+max(0LL,pref[dif][p1]-pref[dif][p3]);
      |                                                                                  ~~~~~~~~~~~~^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 640716 KB Output is correct
2 Correct 250 ms 640628 KB Output is correct
3 Correct 251 ms 640616 KB Output is correct
4 Correct 246 ms 640640 KB Output is correct
5 Correct 240 ms 640604 KB Output is correct
6 Correct 233 ms 640648 KB Output is correct
7 Correct 230 ms 640700 KB Output is correct
8 Correct 226 ms 640636 KB Output is correct
9 Correct 227 ms 640824 KB Output is correct
10 Incorrect 240 ms 640712 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 640716 KB Output is correct
2 Correct 250 ms 640628 KB Output is correct
3 Correct 251 ms 640616 KB Output is correct
4 Correct 246 ms 640640 KB Output is correct
5 Correct 240 ms 640604 KB Output is correct
6 Correct 233 ms 640648 KB Output is correct
7 Correct 230 ms 640700 KB Output is correct
8 Correct 226 ms 640636 KB Output is correct
9 Correct 227 ms 640824 KB Output is correct
10 Incorrect 240 ms 640712 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 640660 KB Output is correct
2 Correct 228 ms 640736 KB Output is correct
3 Correct 252 ms 640712 KB Output is correct
4 Correct 231 ms 640712 KB Output is correct
5 Correct 229 ms 640680 KB Output is correct
6 Correct 251 ms 640688 KB Output is correct
7 Correct 234 ms 640688 KB Output is correct
8 Correct 244 ms 640712 KB Output is correct
9 Correct 240 ms 640744 KB Output is correct
10 Correct 234 ms 640668 KB Output is correct
11 Correct 230 ms 640728 KB Output is correct
12 Correct 233 ms 640660 KB Output is correct
13 Correct 231 ms 640760 KB Output is correct
14 Correct 231 ms 640664 KB Output is correct
15 Incorrect 247 ms 640720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 640716 KB Output is correct
2 Correct 250 ms 640628 KB Output is correct
3 Correct 251 ms 640616 KB Output is correct
4 Correct 246 ms 640640 KB Output is correct
5 Correct 240 ms 640604 KB Output is correct
6 Correct 233 ms 640648 KB Output is correct
7 Correct 230 ms 640700 KB Output is correct
8 Correct 226 ms 640636 KB Output is correct
9 Correct 227 ms 640824 KB Output is correct
10 Incorrect 240 ms 640712 KB Output isn't correct
11 Halted 0 ms 0 KB -