Submission #948990

#	Time	Username	Problem	Language	Result	Execution time	Memory
948990		Zena_Hossam	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	498 ms	103972 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
namespace __gnu_pbds
{
typedef tree<ll,
        null_type,
        less_equal<ll>,
        rb_tree_tag,
        tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define ll double

#define ll1 long long
#define F first
#define S second
#define sz size()
#define all(s) s.begin(),s.end()
#define all1(s) s.rbegin(),s.rend()
int main()
{
    //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout);
    //cin>>T;ll oo=0;

    ll n;
    cin>>n;
    string s;
    cin>>s;
    map<ll,ll>m;
    map<ll,map<ll,ll>>d;
    ll arr[n];
    ll o[3][n];
    o[0][0]=0;
    o[1][0]=0;
    o[2][0]=0;
    for(ll i=0; i<n; i++)
    {
        ll a=0;
        if(s[i]=='R')a=0;
        else if(s[i]=='G')a=1;
        else a=2;
        m[a]++;
        d[a][m[a]]=i;

        if(i)
        {
            o[0][i]=o[0][i-1];
            o[1][i]=o[1][i-1];
            o[2][i]=o[2][i-1];
        }
        o[a][i]+=1;
    }
    ll dp[m[0]+5][m[1]+5][m[2]+5][5];
    for(ll a=0; a<=m[0]+4; a++)
    {
        for(ll b=0; b<=m[1]+4; b++)
        {
            for(ll c=0; c<=m[2]+4; c++)
            {
                    for(ll j=0; j<=4; j++)
                        dp[a][b][c][j]=1e18;
            }
        }
    }
    dp[0][0][0][1]=0;
    dp[0][0][0][0]=0;
    dp[0][0][0][2]=0;
    for(ll c=0; c<=m[2]; c++)
    {
        for(ll a=0; a<=m[0]; a++)
        {
            for(ll b=0; b<=m[1]; b++)
            {ll i=a+b+c;
                if(c<=m[2]&&c>=0)
                {
                    ll xx=0,yy=0,zz=0;
                    ll mx;
                    mx=(d[2][c+1]);
                    xx=max(0ll,c-o[2][mx]);
                    yy=max(0ll,b-o[1][mx]);
                    zz=max(0ll,a-o[0][mx]);

                    dp[a][b][c+1][2]=min(dp[a][b][c+1][2],dp[a][b][c][0]+abs(d[2][c+1]+xx+yy+zz-i));
                    dp[a][b][c+1][2]=min(dp[a][b][c+1][2],dp[a][b][c][1]+abs(d[2][c+1]+xx+yy+zz-i));

                    mx=(d[1][b+1]);
                    xx=max(0ll,c-o[2][mx]);
                    yy=max(0ll,b-o[1][mx]);
                    zz=max(0ll,a-o[0][mx]);

                    dp[a][b+1][c][1]=min(dp[a][b+1][c][1],dp[a][b][c][0]+abs(d[1][b+1]+xx+yy+zz-i));
                    dp[a][b+1][c][1]=min(dp[a][b+1][c][1],dp[a][b][c][2]+abs(d[1][b+1]+xx+yy+zz-i));
                    mx=(d[0][a+1]);
                    xx=max(0ll,c-o[2][mx]);
                    yy=max(0ll,b-o[1][mx]);
                    zz=max(0ll,a-o[0][mx]);

                    dp[a+1][b][c][0]=min(dp[a+1][b][c][0],dp[a][b][c][2]+abs(d[0][a+1]+xx+yy+zz-i));
                    dp[a+1][b][c][0]=min(dp[a+1][b][c][0],dp[a][b][c][1]+abs(d[0][a+1]+xx+yy+zz-i));
                    //}
                }
            }
        }
    }
    for(ll i=0; i<=n; i++)
    {
        for(ll a=0; a<=m[0]; a++)
        {
            for(ll b=0; b<=m[1]; b++)
            {
                ll c=i-a-b;
               // if(c<=m[2])cout<<dp[n][m[0]][m[1]][m[2]][0]<<" "<<dp[n][m[0]][m[1]][m[2]][1]<<" "<<dp[n][m[0]][m[1]][m[2]][2]<<"\n";
            }
        }
    }
    if(min({dp[m[0]][m[1]][m[2]][0],dp[m[0]][m[1]][m[2]][1],dp[m[0]][m[1]][m[2]][2]})==1e18)cout<<-1;
    else
        cout<<min({dp[m[0]][m[1]][m[2]][0],dp[m[0]][m[1]][m[2]][1],dp[m[0]][m[1]][m[2]][2]});
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:115:20: warning: unused variable 'c' [-Wunused-variable]
  115 |                 ll c=i-a-b;
      |                    ^
joi2019_ho_t3.cpp:35:8: warning: unused variable 'arr' [-Wunused-variable]
   35 |     ll arr[n];
      |        ^~~

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