Submission #1120041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120041		AndrijaM	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	119 ms	164876 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

using namespace std;

#define int long long
///#define endl '\n'

const int maxn=400+10;

int dp[maxn][maxn][maxn][3];/// red,green,yellow and what is the last color
int p[maxn][3];

signed main()
{
    ///freopen("detonator.in","r",stdin);
    ///freopen("detonator.out","w",stdout);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int>r;
    vector<int>g;
    vector<int>y;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R')
        {
            r.push_back(i+1);
        }
        if(s[i]=='G')
        {
            g.push_back(i+1);
        }
        if(s[i]=='Y')
        {
            y.push_back(i+1);
        }
        p[i+1][0]=r.size();
        p[i+1][1]=g.size();
        p[i+1][2]=y.size();
    }
    for(int i=0;i<=r.size();i++)
    {
        for(int j=0;j<=g.size();j++)
        {
            for(int k=0;k<=y.size();k++)
            {
                if(i==0 && j==0 && k==0)continue;
                for(int idx=0;idx<3;idx++)
                {
                    dp[i][j][k][idx]=1e9;
                }
                int s=i+k+j;
                if(i!=0)
                {
                    dp[i][j][k][0]=min(dp[i-1][j][k][1],dp[i-1][j][k][2])+((r[i-1]+max(0LL,j-p[r[i-1]][1])+max(0LL,k-p[r[i-1]][2]))-s);
                }
                if(j!=0)
                {
                    dp[i][j][k][1]=min(dp[i][j-1][k][0],dp[i][j-1][k][2])+((g[j-1]+max(0LL,i-p[g[j-1]][0])+max(0LL,k-p[g[j-1]][2]))-s);
                }
                if(k!=0)
                {
                    dp[i][j][k][2]=min(dp[i][j][k-1][0],dp[i][j][k-1][1])+((y[k-1]+max(0LL,i-p[y[k-1]][0])+max(0LL,j-p[y[k-1]][1]))-s);
                }
            }
        }
    }
    int ans = *min_element(dp[r.size()][g.size()][y.size()], dp[r.size()][g.size()][y.size()] + 3);
	if(ans>=1e9)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:43: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]
   43 |     for(int i=0;i<=r.size();i++)
      |                 ~^~~~~~~~~~
joi2019_ho_t3.cpp:45: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]
   45 |         for(int j=0;j<=g.size();j++)
      |                     ~^~~~~~~~~~
joi2019_ho_t3.cpp:47:26: 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]
   47 |             for(int k=0;k<=y.size();k++)
      |                         ~^~~~~~~~~~

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