Submission #1086684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086684		_callmelucian	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	75 ms	193920 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int dp[3][404][404][404];
int pr[404], pg[404], py[404];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, cr = 0, cg = 0, cy = 0; cin >> n;
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == 'R') pr[++cr] = i;
        else if (c == 'G') pg[++cg] = i;
        else py[++cy] = i;
    }

    /*if (cg < cy)
        swap(cg, cy), swap(pg, py);
    if (cr < cg)
        swap(cr, cg), swap(pr, pg);*/

    for (int last = 0; last < 3; last++)
        for (int i = 0; i <= cr; i++)
            for (int j = 0; j <= cg; j++)
                for (int k = 0; k <= cy; k++)
                    dp[last][i][j][k] = INT_MAX;

    dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;

    function<void(int,int,int,int)> refine = [&] (int i, int j, int k, int last) {
        int cur = i + j + k;
        if (last == 0) {
            if (i > 0 && dp[1][i - 1][j][k] != INT_MAX)
                dp[0][i][j][k] = min(dp[0][i][j][k], dp[1][i - 1][j][k] + abs(cur - pr[i]));
            if (i > 0 && dp[2][i - 1][j][k] != INT_MAX)
                dp[0][i][j][k] = min(dp[0][i][j][k], dp[2][i - 1][j][k] + abs(cur - pr[i]));
        }
        else if (last == 1) {
            if (j > 0 && dp[0][i][j - 1][k] != INT_MAX)
                dp[1][i][j][k] = min(dp[1][i][j][k], dp[0][i][j - 1][k] + abs(cur - pg[j]));
            if (j > 0 && dp[2][i][j - 1][k] != INT_MAX)
                dp[1][i][j][k] = min(dp[1][i][j][k], dp[2][i][j - 1][k] + abs(cur - pg[j]));
        }
        else if (last == 2) {
            if (k > 0 && dp[0][i][j][k - 1] != INT_MAX)
                dp[2][i][j][k] = min(dp[2][i][j][k], dp[0][i][j][k - 1] + abs(cur - py[k]));
            if (k > 0 && dp[1][i][j][k - 1] != INT_MAX)
                dp[2][i][j][k] = min(dp[2][i][j][k], dp[1][i][j][k - 1] + abs(cur - py[k]));
        }
    };

    for (int i = 0; i <= cr; i++) {
        for (int j = 0; j <= cg; j++) {
            for (int k = 0; k <= cy; k++) {
                if (!i && !j && !k) continue;
                for (int last = 0; last < 3; last++)
                    refine(i, j, k, last);
            }
        }
    }
    int opt = min({dp[0][cr][cg][cy], dp[1][cr][cg][cy], dp[2][cr][cg][cy]});
    cout << (opt == INT_MAX ? -1 : opt / 2);

    return 0;
}

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