Submission #1275197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275197		nanaseyuzuki	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	123 ms	163072 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 405 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;

int n, prefix[mn][3];
string s;
vector <int> pos[mn];
int dp[405][405][405][4];

int f(int i, int j, int k, int pre){
    if(i + j + k == n) return 0;
    if(dp[i][j][k][pre] != -1) return dp[i][j][k][pre];
    dp[i][j][k][pre] = inf;
    for(int nxt = 0; nxt <= 2; nxt ++){
        if(nxt == pre) continue;
        int cost = 0;
        int p, newi, newj, newk;

        if(nxt == 0){
            if(i + 1 > pos[nxt].size() - 1) continue;
            p = pos[0][i + 1];
            newi = i + 1, newj = j, newk = k;
        }
        
        if(nxt == 1){
            if(j + 1 > pos[nxt].size() - 1) continue;
            p = pos[nxt][j + 1];
            newi = i, newj = j + 1, newk = k;
        }
        
        if(nxt == 2){
            if(k + 1 > pos[nxt].size() - 1) continue;
            p = pos[2][k + 1];
            newi = i, newj = j, newk = k + 1;
        }
        for(int col = 0; col <= 2; col ++){
            if(col == nxt) continue;
            if(col == 0) cost += max(0, prefix[p][col] - i);
            if(col == 1) cost += max(0, prefix[p][col] - j);
            if(col == 2) cost += max(0, prefix[p][col] - k);
        }

        dp[i][j][k][pre] = min(dp[i][j][k][pre], f(newi, newj, newk, nxt) + cost);
    }
    return dp[i][j][k][pre];
}

void solve(){
    cin >> n >> s;
    s = "#" + s;
    for(int i = 0; i <= 2; i++) pos[i].push_back(0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 2; j++) prefix[i][j] = prefix[i - 1][j];
        if(s[i] == 'G'){
            prefix[i][0] ++;
            pos[0].push_back(i);
        }
        if(s[i] == 'R'){
            prefix[i][1] ++;
            pos[1].push_back(i);
        }
        if(s[i] == 'Y'){
            prefix[i][2] ++;
            pos[2].push_back(i);
        }
    }

    for(int i = 0; i <= pos[0].size() - 1; i ++){
        for(int j = 0; j <= pos[1].size() - 1; j++){
            for(int k = 0; k <= pos[2].size() - 1; k++){
                for(int pre = 0; pre <= 3; pre ++){
                    dp[i][j][k][pre] = -1;
                }
            }
        }
    }

    int ans = f(0, 0, 0, 3);
    if(ans == inf) ans = -1;
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

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