Submission #948173

#	Time	Username	Problem	Language	Result	Execution time	Memory
948173		Zena_Hossam	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	739 ms	1048576 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];
    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;
    }
    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++)
            {
                for(ll c=0; c<=m[2]; c++)
                {
                    if(a+b+c==i)
                    {
                       // if(c<m[2])
                       // {
                            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));
                            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));
                        //}
                        //if(b<m[1])
                        //{
                            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));
                            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));
                        //}
                        //if(a<m[0])
                        //{
                            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));
                            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));
                        //}
                    }
                }
            }
        }
    }
    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]})/2;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
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