Submission #671392

#	Time	Username	Problem	Language	Result	Execution time	Memory
671392		GrandTiger1729	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	649 ms	4768 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int key(char c){
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    if (c == 'Y') return 2;
}

const int INF = 1e9 + 9;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    string s; cin >> s;
    vector<int> pos[3];
    for (int i = 0; i < n; i++){
        pos[key(s[i])].push_back(i);
    }
    vector<vector<int>> pref(n + 1, vector<int>(3));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 3; j++){
            pref[i + 1][j] += pref[i][j];
        }
        pref[i + 1][key(s[i])]++;
    }
    int R = pos[0].size(), G = pos[1].size(), Y = pos[2].size();
    auto val = [&](int t, int x, int k){
        return max(0, pref[x][t] - k);
    };
    vector<vector<vector<int>>> dp(R + 1, vector<vector<int>>(G + 1, vector<int>(3, INF)));
    dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 0;
    for (int t = 1; t <= n; t++){
        vector<vector<vector<int>>> tmp(R + 1, vector<vector<int>>(G + 1, vector<int>(3, INF)));
        for (int i = 1; i <= t && i <= R; i++){
            for (int j = 0; i + j <= t && j <= G; j++){
                int k = t - i - j;
                if (k <= Y)
                    tmp[i][j][0] = min(tmp[i][j][0], min(dp[i - 1][j][1], dp[i - 1][j][2]) + val(1, pos[0][i - 1], j) + val(2, pos[0][i - 1], k));
            }
        }
        for (int i = 0; i <= t && i <= R; i++){
            for (int j = 1; i + j <= t && j <= G; j++){
                int k = t - i - j;
                if (k <= Y)
                    tmp[i][j][1] = min(tmp[i][j][1], min(dp[i][j - 1][0], dp[i][j - 1][2]) + val(0, pos[1][j - 1], i) + val(2, pos[1][j - 1], k));
            }
        }
        for (int i = 0; i <= t && i <= R; i++){
            for (int j = 0; i + j <= t && j <= G; j++){
                int k = t - i - j;
                if (0 < k && k <= Y)
                    tmp[i][j][2] = min(tmp[i][j][2], min(dp[i][j][0], dp[i][j][1]) + val(0, pos[2][k - 1], i) + val(1, pos[2][k - 1], j));
            }
        }
        swap(dp, tmp);
    }
    int ans = min({dp[R][G][0], dp[R][G][1], dp[R][G][2]});
    cout << (ans == INF? -1: ans);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int key(char)':
joi2019_ho_t3.cpp:10:1: warning: control reaches end of non-void function [-Wreturn-type]
   10 | }
      | ^

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