제출 #1156922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156922		Pacybwoah	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	389 ms	766724 KiB

joi2019_ho_t3

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
int dp[405][405][405][3];
const int inf = 1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> cols(3, vector<int>(1)), pre(n + 1, vector<int>(3));
    int sr = 0, sg = 0, sb = 0;
    for(int i = 0; i < n; i++){
        pre[i + 1][0] = pre[i][0];
        pre[i + 1][1] = pre[i][1];
        pre[i + 1][2] = pre[i][2];
        if(s[i] == 'R'){
            cols[0].push_back(i + 1);
            sr++;
            pre[i + 1][0]++;
        }
        else if(s[i] == 'G'){
            cols[1].push_back(i + 1);
            sg++;
            pre[i + 1][1]++;
        }
        else{
            cols[2].push_back(i + 1);
            sb++;
            pre[i + 1][2]++;
        }
    }
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) for(int l = 0; l < 3; l++) dp[i][j][k][l] = inf;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    auto mabs = [&](int x){
        return max(x, 0);
    };
    for(int i = 1; i <= n; i++){
        for(int cr = 0; cr <= sr; cr++){
            for(int cg = 0; cg <= sg; cg++){
                for(int col = 0; col < 3; col++){
                    if(i - cr - cg < 0 || i - cr - cg > sb) continue;
                    if(cr == 0 && col == 0) continue;
                    if(cg == 0 && col == 1) continue;
                    if(i - cr - cg == 0 && col == 2) continue;
                    int cost, cb = i - cr - cg;
                    if(col == 0) cost = mabs(pre[cols[0][cr]][1] - cg) + mabs(pre[cols[0][cr]][2] - cb);
                    else if(col == 1) cost = mabs(pre[cols[1][cg]][0] - cr) + mabs(pre[cols[1][cg]][2] - cb);
                    else cost = mabs(pre[cols[2][cb]][0] - cr) + mabs(pre[cols[2][cb]][1] - cg);
                    int dpc = inf;
                    for(int k = 0; k < 3; k++){
                        if(k != col){
                            if(col == 0) dpc = min(dpc, dp[i - 1][cr - 1][cg][k] + cost);
                            else if(col == 1) dpc = min(dpc, dp[i - 1][cr][cg - 1][k] + cost);
                            else dpc = min(dpc, dp[i - 1][cr][cg][k] + cost);
                        }
                    }
                    dp[i][cr][cg][col] = dpc;
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[n][sr][sg][i]);
    if(ans == inf) cout << "-1\n";
    else cout << ans << "\n";
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pC.cpp

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