Submission #936047

#	Time	Username	Problem	Language	Result	Execution time	Memory
936047		Marco_Escandon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	135 ms	77984 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct st{ ll a,b,c; };
vector<st> cad[4];
ll cost(ll p1, ll p2, st asd, ll p)
{
    asd.a=max(cad[p1][p2].a,asd.a-1);
    asd.b=max(cad[p1][p2].b,asd.b-1);
    asd.c=max(cad[p1][p2].c,asd.c-1);
    return (asd.a+asd.b+asd.c-p);
}
int main()
{
    ll n;
    cin>>n;
    st asd={0,0,0};
    for(int i=0; i<4; i++)
        cad[i].push_back(asd),cad[i].push_back(asd);
    for(int i=1; i<=n; i++)
    {
        char temp;
        cin>>temp;
        if(temp=='R') asd.a++;
        if(temp=='G') asd.b++;
        if(temp=='Y') asd.c++;
        if(temp=='R') cad[1].push_back(asd);
        if(temp=='G') cad[2].push_back(asd);
        if(temp=='Y') cad[3].push_back(asd);
    }
    ll dp[4][cad[1].size()][cad[2].size()][cad[3].size()];
    
    for(int i=0; i<cad[1].size(); i++)
        for(int j=0; j<cad[2].size(); j++)
            for(int k=0; k<cad[3].size(); k++)
            dp[1][i][j][k]=dp[2][i][j][k]=dp[3][i][j][k]=1e9;
    dp[1][1][1][1]=0;
    dp[2][1][1][1]=0;
    dp[3][1][1][1]=0;
    ll sol=0;
    for(int i=1; i<cad[1].size(); i++)
    {
        for(int j=1; j<cad[2].size(); j++)
        {
            for(int k=1; k<cad[3].size(); k++)
            {
                ll asd=1e9;
                if(i+j+k<=3) continue;
                for(int pl=1; pl<4; pl++)
                {
                    ll temp=1e9;
                    if(pl==1)
                    {
                        if(j>1)
                        temp=min(temp,dp[2][i][j-1][k]+cost(2,j,{i,j,k},i+j+k-3));
                        if(k>1)
                        temp=min(temp,dp[3][i][j][k-1]+cost(3,k,{i,j,k},i+j+k-3));
                    }
                    if(pl==2)
                    {
                        if(i>1)
                        temp=min(temp,dp[1][i-1][j][k]+cost(1,i,{i,j,k},i+j+k-3));
                        if(k>1)
                        temp=min(temp,dp[3][i][j][k-1]+cost(3,k,{i,j,k},i+j+k-3));
                    }
                    if(pl==3)
                    {
                        if(i>1)
                        temp=min(temp,dp[1][i-1][j][k]+cost(1,i,{i,j,k},i+j+k-3));
                        if(j>1)
                        temp=min(temp,dp[2][i][j-1][k]+cost(2,j,{i,j,k},i+j+k-3));
                    }
                    asd=min(asd,temp);
                    dp[pl][i][j][k]=min(temp,dp[pl][i][j][k]);
                }
                sol=asd;
            }
        }
    }
    if(sol==1000000000)
    {
        cout<<"-1";
    }
    else {
        cout<<sol;
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0; i<cad[1].size(); i++)
      |                  ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j=0; j<cad[2].size(); j++)
      |                      ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int k=0; k<cad[3].size(); k++)
      |                          ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=1; i<cad[1].size(); i++)
      |                  ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j=1; j<cad[2].size(); j++)
      |                      ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int k=1; k<cad[3].size(); k++)
      |                          ~^~~~~~~~~~~~~~

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