Submission #900143

#	Time	Username	Problem	Language	Result	Execution time	Memory
900143		andrei_iorgulescu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	76 ms	412004 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

int inf = 1e8;
int n;
int a[405];
char sir[405];
int dp[401][401][401][4];
int pos[3][405],p0,p1,p2;
int sp[3][405];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> sir[i];
    for (int i = 1; i <= n; i++)
    {
        if (sir[i] == 'R')
        {
            a[i] = 0;
            pos[0][++p0] = i;
        }
        else if (sir[i] == 'G')
        {
            a[i] = 1;
            pos[1][++p1] = i;
        }
        else
        {
            a[i] = 2;
            pos[2][++p2] = i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
            sp[j][i] = sp[j][i - 1];
        sp[a[i]][i]++;
    }
    for (int i = 0; i <= p0; i++)
        for (int j = 0; j <= p1; j++)
            for (int q = 0; q <= p2; q++)
                for (int c = 0; c < 3; c++)
                    dp[i][j][q][c] = inf;
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 0; i <= p0; i++)
    {
        for (int j = 0; j <= p1; j++)
        {
            for (int q = 0; q <= p2; q++)
            {
                if (i < p0)
                {
                    int pz = pos[0][i + 1];
                    dp[i + 1][j][q][0] = min(dp[i + 1][j][q][0],min(dp[i][j][q][1],dp[i][j][q][2]) + abs(j - sp[1][pz]) + abs(q - sp[2][pz]));
                }
                if (j < p1)
                {
                    int pz = pos[1][j + 1];
                    dp[i][j + 1][q][1] = min(dp[i][j + 1][q][1],min(dp[i][j][q][0],dp[i][j][q][2]) + abs(i - sp[0][pz]) + abs(q - sp[2][pz]));
                }
                if (q < p2)
                {
                    int pz = pos[2][q + 1];
                    dp[i][j][q + 1][2] = min(dp[i][j][q + 1][2],min(dp[i][j][q][0],dp[i][j][q][1]) + abs(i - sp[0][pz]) + abs(j - sp[1][pz]));
                }
            }
        }
    }
    int ans = min(dp[p0][p1][p2][0],min(dp[p0][p1][p2][1],dp[p0][p1][p2][2]));
    if (ans >= inf / 2)
        cout << -1;
    else
        cout << ans / 2;
    return 0;
}

///dp[i][j][q][c] bla bla

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