Submission #123059

#	Time	Username	Problem	Language	Result	Execution time	Memory
123059		Alliance	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	839 ms	567004 KiB

joi2019_ho_t3

// In the Name of Allah
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 70;
const ll MOD = 1e9+7;
using namespace std;

int dp[MAX_N][MAX_N][MAX_N][MAX_N][3];
int a[MAX_N];
int n;

void readinput()
{
    cin >> n;
    string s;
    cin >> s;
    for(int i = 1;i<=n;++i)
    {
        if (s[i-1]=='R')
            a[i] = 0;
        else if (s[i-1]=='G')
            a[i] = 1;
        else
            a[i] = 2;
    }
}

void mini(int &a,int b)
{
    a = min(a,b);
}

int main()
{
    readinput();
    for(int i = 0;i<MAX_N;++i)
        for(int j = 0;j<MAX_N;++j)
            for(int k = 0;k<MAX_N;++k)
                for(int t = 0;t<MAX_N;++t)
                    for(int l = 0;l<3;++l)
                        dp[i][j][k][t][l] = 1e9;
    dp[1][0][0][0][a[1]] = 0;
    for(int i = 2;i<=n;++i)
    {
        for(int x1 = 0;x1<i;++x1)
        {
            for(int x2 = 0;x2<i;++x2)
            {
                for(int x3 = 0;x3<i;++x3)
                {
                    for(int j = 0;j<3;++j)
                    {
                        int s = x1+x2+x3;
                        if (j==a[i])
                        {
                            if (a[i]==0)
                                mini(dp[i][x1+1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s+1);
                            if (a[i]==1)
                                mini(dp[i][x1][x2+1][x3][j],dp[i-1][x1][x2][x3][j]+s+1);
                            if (a[i]==2)
                                mini(dp[i][x1][x2][x3+1][j],dp[i-1][x1][x2][x3][j]+s+1);
                        }
                        else
                            mini(dp[i][x1][x2][x3][a[i]],dp[i-1][x1][x2][x3][j]+s);
                        if (a[i]==0)
                        {
                            if (x2)
                                mini(dp[i][x1][x2-1][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x3)
                                mini(dp[i][x1][x2][x3-1][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                        else if (a[i]==1)
                        {
                            if (x1)
                                mini(dp[i][x1-1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x3)
                                mini(dp[i][x1][x2][x3-1][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                        else
                        {
                            if (x2)
                                mini(dp[i][x1][x2-1][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x1)
                                mini(dp[i][x1-1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                    }
                }
            }
        }
    }
    vector<int> vc;
    for(int i = 0;i<3;++i)
    {
        if (dp[n][0][0][0][i]<=n*n*n)
            vc.push_back(dp[n][0][0][0][i]);
    }
    if (!vc.size())
        cout << -1;
    else
    {
        sort(vc.begin(),vc.end());
        cout << vc[0];
    }
    return 0;
}

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