제출 #671390

#제출 시각아이디문제언어결과실행 시간메모리
671390GrandTiger1729Growing Vegetable is Fun 3 (JOI19_ho_t3)C++17
60 / 100
1081 ms17864 KiB
#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);
    }
    int R = pos[0].size(), G = pos[1].size(), Y = pos[2].size();
    auto val = [&](vector<int> &a, int x, int k){
        int ret = lower_bound(a.begin(), a.end(), x) - a.begin();
        return max(0, ret - k);
    };
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 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(n + 1, vector<vector<int>>(n + 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(pos[1], pos[0][i - 1], j) + val(pos[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(pos[0], pos[1][j - 1], i) + val(pos[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(pos[0], pos[2][k - 1], i) + val(pos[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) << '\n';
    return 0;
}

컴파일 시 표준 에러 (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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...