Submission #735143

#	Time	Username	Problem	Language	Result	Execution time	Memory
735143		1075508020060209tc	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	177 ms	164840 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n;
string inps;
int ar[510];
int dp[410][410][410][3];
vector<int>e[3];
int difc[510][3];


void upd(int A,int B,int C,int tl,int a,int b,int c,int tll){
if(A>e[0].size()){return;}
if(B>e[1].size()){return;}
if(C>e[2].size()){return;}
int cal=dp[a][b][c][tll];
int i=A+B+C;
cal-=i;
int pl;
int us=0;
if(tl==0){pl=e[0][A-1];us=max(B-difc[pl][1],0ll)+max(C-difc[pl][2],0ll);  }
if(tl==1){pl=e[1][B-1];us=max(A-difc[pl][0],0ll)+max(C-difc[pl][2],0ll);  }
if(tl==2){pl=e[2][C-1];us=max(B-difc[pl][1],0ll)+max(A-difc[pl][0],0ll);  }
cal+=pl;
cal+=us;
dp[A][B][C][tl]=min(dp[A][B][C][tl],cal);
}


signed main(){
cin>>n>>inps;
for(int i=0;i<n;i++){
    if(inps[i]=='R'){
        ar[i+1]=0;
    }
    if(inps[i]=='G'){
        ar[i+1]=1;
    }
    if(inps[i]=='Y'){
        ar[i+1]=2;
    }
}
for(int i=1;i<=n;i++){
    e[ar[i]].push_back(i);
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
        if(ar[j]!=ar[i]){
            difc[i][ar[j]]++;
        }
    }
}
for(int a=0;a<=e[0].size();a++){
    for(int b=0;b<=e[1].size();b++){
        for(int c=0;c<=e[2].size();c++){
            dp[a][b][c][0]=1e9;
            dp[a][b][c][1]=1e9;
            dp[a][b][c][2]=1e9;
        }
    }
}
if(e[0].size()){
    dp[1][0][0][0]=e[0][0]-1;
}
if(e[1].size()){
    dp[0][1][0][1]=e[1][0]-1;
}
if(e[2].size()){
    dp[0][0][1][2]=e[2][0]-1;
}

for(int a=0;a<=e[0].size();a++){
    for(int b=0;b<=e[1].size();b++){
        for(int c=0;c<=e[2].size();c++){
            upd(a,b,c+1,2,a,b,c,0);
            upd(a,b+1,c,1,a,b,c,0);
            upd(a+1,b,c,0,a,b,c,1);
            upd(a,b,c+1,2,a,b,c,1);
            upd(a+1,b,c,0,a,b,c,2);
            upd(a,b+1,c,1,a,b,c,2);
        }
    }
}
int ans=min({dp[e[0].size()][e[1].size()][e[2].size()][0],dp[e[0].size()][e[1].size()][e[2].size()][1],dp[e[0].size()][e[1].size()][e[2].size()][2]});
if(ans==1e9){ans=-1;}
cout<<ans<<endl;
int a;int b;int c;
return 0;
while(cin>>a>>b>>c){

    cout<<dp[a][b][c][0]<<" "<<dp[a][b][c][1]<<" "<<dp[a][b][c][2]<<endl;

}


}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:14:5: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | if(A>e[0].size()){return;}
      |    ~^~~~~~~~~~~~
joi2019_ho_t3.cpp:15:5: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | if(B>e[1].size()){return;}
      |    ~^~~~~~~~~~~~
joi2019_ho_t3.cpp:16:5: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | if(C>e[2].size()){return;}
      |    ~^~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:54:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 | for(int a=0;a<=e[0].size();a++){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int b=0;b<=e[1].size();b++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int c=0;c<=e[2].size();c++){
      |                     ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:73:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 | for(int a=0;a<=e[0].size();a++){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int b=0;b<=e[1].size();b++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:75:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int c=0;c<=e[2].size();c++){
      |                     ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:25:4: warning: 'pl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 | cal+=pl;
      | ~~~^~~~

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