Submission #948787

#	Time	Username	Problem	Language	Result	Execution time	Memory
948787		Zena_Hossam	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1 ms	604 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[n+5][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 i=0; i<=n+4; i++)
                {
                    for(ll j=0; j<=4; j++)
                        dp[i][a][b][c][j]=1e18;
                }
            }
        }
    }
    dp[0][0][0][0][1]=0;
    dp[0][0][0][0][0]=0;
    dp[0][0][0][0][2]=0;
    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]&&c>=0)
                {
                    // if(c<m[2])
                    // {
                    ll xx=0,yy=0,zz=0;
                    ll maxIndex = max(i-1, d[2][c+1]-1);
                    xx = min(c, o[2][maxIndex]);

                    if (i && d[2][c+1])
                    {
                        ll minIndex = min(i-1, d[2][c+1]-1);
                        xx -= (o[2][minIndex]);
                    }

                    maxIndex = max(i-1, d[2][c+1]-1);
                    yy = min(c, o[1][maxIndex]);

                    if (i && d[2][c+1])
                    {
                        ll minIndex = min(i-1, d[2][c+1]-1);
                        yy -= min(c, o[1][minIndex]);
                    }

                    maxIndex = max(i-1, d[2][c+1]-1);
                    zz = min(c, o[0][maxIndex]);

                    if (i && d[2][c+1])
                    {
                        ll minIndex = min(i-1, d[2][c+1]-1);
                        zz -= min(c, o[0][minIndex]);
                    }
                   //cout<<xx<<" "<<yy<<" "<<zz<<" "<<d[2][c+1]<<" "<<i<<'\n';
                    dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][0]+abs(d[2][c+1]-i)-xx-yy-zz);
                    dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][1]+abs(d[2][c+1]-i)-xx-yy-zz);
                    //}
                    //if(b<m[1])
                    //{
                    maxIndex = max(i-1, d[1][b+1]-1);
                    xx = min(c, o[2][maxIndex]);

                    if (i && d[1][b+1])
                    {
                        ll minIndex = min(i-1, d[1][b+1]-1);
                        xx -= (o[2][minIndex]);
                    }

                    maxIndex = max(i-1, d[1][b+1]-1);
                    yy = min(c, o[1][maxIndex]);

                    if (i && d[1][b+1])
                    {
                        ll minIndex = min(i-1, d[1][b+1]-1);
                        yy -= min(c, o[1][minIndex]);
                    }

                    maxIndex = max(i-1, d[1][b+1]-1);
                    zz = min(c, o[0][maxIndex]);

                    if (i && d[1][b+1])
                    {
                        ll minIndex = min(i-1, d[1][b+1]-1);
                        zz -= min(c, o[0][minIndex]);
                    }

                    dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][0]+abs(d[1][b+1]-i)-xx-yy-zz);
                    dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][2]+abs(d[1][b+1]-i)-xx-yy-zz);
                    //}
                    //if(a<m[0])
                    //{
                    maxIndex = max(i-1, d[0][a+1]-1);
                    xx = min(c, o[2][maxIndex]);

                    if (i && d[0][a+1])
                    {
                        ll minIndex = min(i-1, d[0][a+1]-1);
                        xx -= (o[2][minIndex]);
                    }

                    maxIndex = max(i-1, d[0][a+1]-1);
                    yy = min(c, o[1][maxIndex]);

                    if (i && d[0][a+1])
                    {
                        ll minIndex = min(i-1, d[0][a+1]-1);
                        yy -= min(c, o[1][minIndex]);
                    }

                    maxIndex = max(i-1, d[0][a+1]-1);
                    zz = min(c, o[0][maxIndex]);

                    if (i && d[0][a+1])
                    {
                        ll minIndex = min(i-1, d[0][a+1]-1);
                        zz -= min(c, o[0][minIndex]);
                    }

                    dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][2]+abs(d[0][a+1]-i)-xx-yy-zz);
                    dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][1]+abs(d[0][a+1]-i)-xx-yy-zz);
                    //}
                }
            }
        }
    }
    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[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]})==1e18)cout<<-1;
    else
        cout<<min({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]});
}

Compilation message (stderr)

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

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