Submission #1156910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156910		Pacybwoah	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	446 ms	766772 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));
    int sr = 0, sg = 0, sb = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R'){
            cols[0].push_back(i + 1);
            sr++;
        }
        else if(s[i] == 'G'){
            cols[1].push_back(i + 1);
            sg++;
        }
        else{
            cols[2].push_back(i + 1);
            sb++;
        }
    }
    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;
    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;
                    if(col == 0) cost = abs(cols[col][cr] - i);
                    else if(col == 1) cost = abs(cols[col][cg] - i);
                    else cost = abs(cols[col][i - cr - cg] - i);
                    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 / 2 << "\n";
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pC.cpp

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