Submission #557000

#	Time	Username	Problem	Language	Result	Execution time	Memory
557000		alextodoran	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	66 ms	162944 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], cnta;
int B[N_MAX + 2], cntb;
int C[N_MAX + 2], 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] = i - (cnta - 1);
        } else if (S[i] == 'G') {
            cntb++;
            B[cntb] = i - (cntb - 1);
        } else {
            cntc++;
            C[cntc] = i - (cntc - 1);
        }
    }

    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 + c - A[a + 1]));
                }
                if (b < cntb) {
                    update(dp[a][b + 1][c][1], min(dp[a][b][c][0], dp[a][b][c][2]) + abs(c + a - B[b + 1]));
                }
                if (c < cntc) {
                    update(dp[a][b][c + 1][2], min(dp[a][b][c][1], dp[a][b][c][0]) + abs(a + b - C[c + 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: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25