Submission #557004

#	Time	Username	Problem	Language	Result	Execution time	Memory
557004		alextodoran	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	73 ms	162976 KiB

joi2019_ho_t3

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 400;

int N;
string S;

int A[N_MAX + 2][3], cnta;
int B[N_MAX + 2][3], cntb;
int C[N_MAX + 2][3], cntc;

int dp[N_MAX + 2][N_MAX + 2][N_MAX + 2][3];

void update (int &x, const int &y) {
    if (y < x) {
        x = y;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> S;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'R') {
            cnta++;
            A[cnta][1] = cntb;
            A[cnta][2] = cntc;
        } else if (S[i] == 'G') {
            cntb++;
            B[cntb][2] = cntc;
            B[cntb][0] = cnta;
        } else {
            cntc++;
            C[cntc][0] = cnta;
            C[cntc][1] = cntb;
        }
    }

    for (int a = 0; a <= cnta; a++) {
        for (int b = 0; b <= cntb; b++) {
            for (int c = 0; c <= cntc; c++) {
                dp[a][b][c][0] = INT_MAX / 2;
                dp[a][b][c][1] = INT_MAX / 2;
                dp[a][b][c][2] = INT_MAX / 2;
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for (int a = 0; a <= cnta; a++) {
        for (int b = 0; b <= cntb; b++) {
            for (int c = 0; c <= cntc; c++) {
                if (a < cnta) {
                    update(dp[a + 1][b][c][0], min(dp[a][b][c][2], dp[a][b][c][1]) + abs(b - A[a + 1][1]) + abs(c - A[a + 1][2]));
                }
                if (b < cntb) {
                    update(dp[a][b + 1][c][1], min(dp[a][b][c][0], dp[a][b][c][2]) + abs(c - B[b + 1][2]) + abs(a - B[b + 1][0]));
                }
                if (c < cntc) {
                    update(dp[a][b][c + 1][2], min(dp[a][b][c][1], dp[a][b][c][0]) + abs(a - C[c + 1][0]) + abs(b - C[c + 1][1]));
                }
            }
        }
    }
    int answer = INT_MAX / 2;
    answer = min(answer, dp[cnta][cntb][cntc][0]);
    answer = min(answer, dp[cnta][cntb][cntc][1]);
    answer = min(answer, dp[cnta][cntb][cntc][2]);
    cout << (answer != INT_MAX / 2 ? answer / 2 : -1) << "\n";

    return 0;
}

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