Submission #738443

#	Time	Username	Problem	Language	Result	Execution time	Memory
738443		Ahmed57	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	419 ms	1048576 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;
long long dp[3][401][401][401];
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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25