Submission #1171452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171452		chikien2009	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	60 ms	162888 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, f[401][401][401][3], pre[3][401];
vector<int> p[3];
string s;

int main()
{
    setup();

    cin >> n >> s;
    s = '#' + s;
    p[0] = {0};
    p[1] = {0};
    p[2] = {0};
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == 'R')
        {
            p[0].push_back(i);
        }
        else if (s[i] == 'G')
        {
            p[1].push_back(i);
        }
        else
        {
            p[2].push_back(i);
        }
        pre[0][i] = p[0].size();
        pre[1][i] = p[1].size();
        pre[2][i] = p[2].size();
    }
    for (int i = 0; i < p[0].size(); ++i)
    {
        for (int j = 0; j < p[1].size(); ++j)
        {
            for (int k = 0; k < p[2].size(); ++k)
            {
                if (i + j + k == 0)
                {
                    f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = 0;
                    continue;
                }
                f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = 2e9;
                if (0 < i)
                {
                    f[i][j][k][0] = min(f[i - 1][j][k][1], f[i - 1][j][k][2]) + p[0][i] - i - j - k;
                    f[i][j][k][0] += max(0, pre[1][p[1][j]] - pre[1][p[0][i]]);
                    f[i][j][k][0] += max(0, pre[2][p[2][k]] - pre[2][p[0][i]]);
                }
                if (0 < j)
                {
                    f[i][j][k][1] = min(f[i][j - 1][k][0], f[i][j - 1][k][2]) + p[1][j] - i - j - k;
                    f[i][j][k][1] += max(0, pre[0][p[0][i]] - pre[0][p[1][j]]);
                    f[i][j][k][1] += max(0, pre[2][p[2][k]] - pre[2][p[1][j]]);
                }
                if (0 < k)
                {
                    f[i][j][k][2] = min(f[i][j][k - 1][0], f[i][j][k - 1][1]) + p[2][k] - i - j - k;
                    f[i][j][k][2] += max(0, pre[0][p[0][i]] - pre[0][p[2][k]]);
                    f[i][j][k][2] += max(0, pre[1][p[1][j]] - pre[1][p[2][k]]);
                }
                if (i + j + k == n)
                {
                    n = min({f[i][j][k][0], f[i][j][k][1], f[i][j][k][2]});
                }
            }
        }
    }
    cout << (n > 1e9 ? -1 : n);
    return 0;
}

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