Submission #1275189

#TimeUsernameProblemLanguageResultExecution timeMemory
1275189nanaseyuzukiGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
552 ms1114112 KiB
#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

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

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

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(0ll, prefix[p][col] - i);
            if(col == 1) cost += max(0ll, prefix[p][col] - j);
            if(col == 2) cost += max(0ll, 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);
        }
    }
    memset(dp, -1, sizeof(dp));
    int ans = f(0, 0, 0, 4);
    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();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...