Submission #936957

#	Time	Username	Problem	Language	Result	Execution time	Memory
936957		Maite_Morale	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	361 ms	224340 KiB

joi2019_ho_t3

    #include<bits/stdc++.h>
    #define F first
    #define S second
    #define MAX 405
    #define oo 1e18
    #define mod 1000000007
    #define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
    using namespace std;
    typedef long long ll;
    #define pll pair<ll , ll>
    #define vll vector<ll>
    #define vvll vector<vll>
    #define vpll vector<pll>
     
    ll n,t[5][405];
    vll v[5];
    string a;
    ll dp[400][400][400][3],s[10]={0,0,0};
    ll cost(vll x,ll z){
        ll r=0;ll p=v[z][x[z]-1]-1;
        for(int i=0;i<3;i++){
            if(i==z)continue;
            r+=max(0LL,t[i][p]-x[i]);
        }
    return r;
    }
    int main(){
        fast_in
        cin>>n>>a;
        for(int i=0;i<n;i++){
            if(a[i]=='R'){v[0].push_back(i+1);t[0][i]++;}
            if(a[i]=='G'){v[1].push_back(i+1);t[1][i]++;}
            if(a[i]=='Y'){v[2].push_back(i+1);t[2][i]++;}
            if(i==0)continue;
            t[0][i]+=t[0][i-1];
            t[1][i]+=t[1][i-1];
            t[2][i]+=t[2][i-1];
        }
        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++){
                    for(int h=0;h<3;h++){
                        if(i+j+k==0){
                            dp[i][j][k][h]=0;
                          //  cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<".\n";
                            continue;
                        }
                        s[h]=1;dp[i][j][k][h]=oo;
                        if(min(i-s[0],min(j-s[1],k-s[2]))<0){
                            s[h]=0;
                           // cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"_\n";
                            continue;
                        }
                        for(int h1=0;h1<3;h1++){
                            if(h1==h)continue;
                            ll z=dp[i][j][k][h],w=dp[i-s[0]][j-s[1]][k-s[2]][h1],w1=cost({i,j,k},h);
                            dp[i][j][k][h]=min(z,w+w1);
                        }
                       // cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"\n";
                        s[h]=0;
                    }
                }
            }
        }
        sort(dp[v[0].size()][v[1].size()][v[2].size()],dp[v[0].size()][v[1].size()][v[2].size()]+3);
        if(dp[v[0].size()][v[1].size()][v[2].size()][0]==oo)dp[v[0].size()][v[1].size()][v[2].size()][0]=-1;
        cout<<dp[v[0].size()][v[1].size()][v[2].size()][0];
    return 0;
    }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0;i<=v[0].size();i++){
      |                     ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int j=0;j<=v[1].size();j++){
      |                         ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 for(int k=0;k<=v[2].size();k++){
      |                             ~^~~~~~~~~~~~~

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