Submission #391336

#	Time	Username	Problem	Language	Result	Execution time	Memory
391336		timmyfeng	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	92 ms	162932 KiB

joi2019_ho_t3

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

const int N = 401;

int count_r[N], count_g[N], count_y[N];
int where_r[N], where_g[N], where_y[N];
int swaps[N][N][N][3];

void set_min(int &a, int b) {
    a = min(a, b);
}

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

    int n;
    string s;
    cin >> n >> s;

    for (int i = 0; i < n; ++i) {
        count_r[i + 1] = count_r[i] + (s[i] == 'R');
        count_g[i + 1] = count_g[i] + (s[i] == 'G');
        count_y[i + 1] = count_y[i] + (s[i] == 'Y');

        if (s[i] == 'R') {
            where_r[count_r[i]] = i;
        } else if (s[i] == 'G') {
            where_g[count_g[i]] = i;
        } else {
            where_y[count_y[i]] = i;
        }
    }

    for (int r = 0; r <= count_r[n]; ++r) {
        for (int g = 0; g <= count_g[n]; ++g) {
            for (int y = 0; y <= count_y[n]; ++y) {
                for (int i = 0; i < 3; ++i) {
                    if (r + g + y > 0) {
                        swaps[r][g][y][i] = INT_MAX;
                    }
                }
            }
        }
    }

    for (int r = 0; r <= count_r[n]; ++r) {
        for (int g = 0; g <= count_g[n]; ++g) {
            for (int y = 0; y <= count_y[n]; ++y) {
                for (int i = 0; i < 3; ++i) {
                    if (swaps[r][g][y][i] < INT_MAX) {
                        if (i != 0 && r < count_r[n]) {
                            set_min(swaps[r + 1][g][y][0], swaps[r][g][y][i] +
                                max(0, count_g[where_r[r]] - g) +
                                max(0, count_y[where_r[r]] - y)
                            );
                        }

                        if (i != 1 && g < count_g[n]) {
                            set_min(swaps[r][g + 1][y][1], swaps[r][g][y][i] +
                                max(0, count_r[where_g[g]] - r) +
                                max(0, count_y[where_g[g]] - y)
                            );
                        }

                        if (i != 2 && y < count_y[n]) {
                            set_min(swaps[r][g][y + 1][2], swaps[r][g][y][i] +
                                max(0, count_r[where_y[y]] - r) +
                                max(0, count_g[where_y[y]] - g)
                            );
                        }
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i < 3; ++i) {
        set_min(ans, swaps[count_r[n]][count_g[n]][count_y[n]][i]);
    }

    cout << (ans < INT_MAX ? ans : -1) << "\n";
}

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