Submission #232229

#	Time	Username	Problem	Language	Result	Execution time	Memory
232229		Andrei_Cotor	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	103 ms	194352 KiB

joi2019_ho_t3

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> Poz[3];
vector<pair<int,int> > Coresp[3];
int Dp[3][405][405][405];

int getSwaps(int wh, int fir, int sec, int i, int j, int k)
{
    int rez=0;
    rez=rez+max(0,Coresp[wh][i-1].first-j+1); //cati fir au ramas neasezati pana la i
    rez=rez+max(0,Coresp[wh][i-1].second-k+1);
    return rez;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        char c;
        cin>>c;

        if(c=='R')
        {
            Poz[0].push_back(i);
            Coresp[0].push_back({Poz[1].size()-1,Poz[2].size()-1});
        }
        else if(c=='G')
        {
            Poz[1].push_back(i);
            Coresp[1].push_back({Poz[0].size()-1,Poz[2].size()-1});
        }
        else
        {
            Poz[2].push_back(i);
            Coresp[2].push_back({Poz[0].size()-1,Poz[1].size()-1});
        }
    }

    for(int i=0; i<=Poz[0].size(); i++)
    {
        for(int j=0; j<=Poz[1].size(); j++)
        {
            for(int k=0; k<=Poz[2].size(); k++)
            {
                Dp[0][i][j][k]=Dp[1][i][j][k]=Dp[2][i][j][k]=1000000000;
            }
        }
    }

    Dp[0][0][0][0]=Dp[1][0][0][0]=Dp[2][0][0][0]=0;
    for(int i=0; i<=Poz[0].size(); i++)
    {
        for(int j=0; j<=Poz[1].size(); j++)
        {
            for(int k=0; k<=Poz[2].size(); k++)
            {
                if(i<Poz[0].size())
                {
                    Dp[0][i+1][j][k]=min(Dp[0][i+1][j][k],min(Dp[1][i][j][k],Dp[2][i][j][k])+getSwaps(0,1,2,i+1,j,k));
                }
                
                if(j<Poz[1].size())
                {
                    Dp[1][i][j+1][k]=min(Dp[1][i][j+1][k],min(Dp[0][i][j][k],Dp[2][i][j][k])+getSwaps(1,0,2,j+1,i,k));
                }

                if(k<Poz[2].size())
                {
                    Dp[2][i][j][k+1]=min(Dp[2][i][j][k+1],min(Dp[0][i][j][k],Dp[1][i][j][k])+getSwaps(2,0,1,k+1,i,j));
                }
            }
        }
    }

    int rez=min(Dp[0][Poz[0].size()][Poz[1].size()][Poz[2].size()],min(Dp[1][Poz[0].size()][Poz[1].size()][Poz[2].size()],Dp[2][Poz[0].size()][Poz[1].size()][Poz[2].size()]));
    if(rez==1000000000)
        rez=-1;

    cout<<rez<<"\n";
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<=Poz[0].size(); i++)
                  ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<=Poz[1].size(); j++)
                      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<=Poz[2].size(); k++)
                          ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<=Poz[0].size(); i++)
                  ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<=Poz[1].size(); j++)
                      ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0; k<=Poz[2].size(); k++)
                          ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i<Poz[0].size())
                    ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j<Poz[1].size())
                    ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(k<Poz[2].size())
                    ~^~~~~~~~~~~~~~

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