Submission #1086837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086837		_callmelucian	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	66 ms	97104 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())

const int G = 'G';
const int R = 'R';
const int Y = 'Y';

int dp[3][404][202][202], pre[101][404], pos[101][404];

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

    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        pre[G][i] = pre[G][i - 1];
        pre[R][i] = pre[R][i - 1];
        pre[Y][i] = pre[Y][i - 1];

        char c; cin >> c;
        pos[c][++pre[c][i]] = i;
    }

    if (pre[R][n] < pre[Y][n])
        swap(pre[R], pre[Y]), swap(pos[R], pos[Y]);
    if (pre[G][n] < pre[R][n])
        swap(pre[G], pre[R]), swap(pos[G], pos[R]);

    for (int type = 0; type < 3; type++)
        for (int i = 0; i <= pre[G][n]; i++)
            for (int j = 0; j <= pre[R][n]; j++)
                for (int k = 0; k <= pre[Y][n]; k++)
                    dp[type][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 type) {
        if (type == 0 && i > 0) {
            int startPos = pos[G][i], cost = max(0, pre[R][startPos] - j) + max(0, pre[Y][startPos] - k);

            if (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] + cost);

            if (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] + cost);
        }

        else if (type == 1 && j > 0) {
            int startPos = pos[R][j], cost = max(0, pre[G][startPos] - i) + max(0, pre[Y][startPos] - k);

            if (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] + cost);

            if (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] + cost);
        }

        else if (type == 2 && k > 0) {
            int startPos = pos[Y][k], cost = max(0, pre[G][startPos] - i) + max(0, pre[R][startPos] - j);

            if (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] + cost);

            if (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] + cost);
        }
    };

    for (int i = 0; i <= pre[G][n]; i++) {
        for (int j = 0; j <= pre[R][n]; j++) {
            for (int k = 0; k <= pre[Y][n]; k++) {
                if (!i && !j && !k) continue;
                for (int type = 0; type < 3; type++) refine(i, j, k, type);
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i < 3; i++) ans = min(ans, dp[i][pre[G][n]][pre[R][n]][pre[Y][n]]);
    cout << (ans == INT_MAX ? -1 : ans);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         pos[c][++pre[c][i]] = i;
      |             ^
joi2019_ho_t3.cpp:31:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         pos[c][++pre[c][i]] = i;
      |                      ^

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