Submission #762256

#	Time	Username	Problem	Language	Result	Execution time	Memory
762256		sysia	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	130 ms	84236 KiB

joi2019_ho_t3

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
// #define int long long
typedef pair<int, int> T;
const int oo = 1e9+7, oo2 = 1e9+7, K = 30;
 
int ti(char c){
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    return 2;
}
 
void ckmin(int &a, int b){
    a = min(a, b);
}
 
void solve(){
    int n; cin >> n;
    string s; cin >> s;
    vector<int>cnt(3);
    for (auto c: s) cnt[ti(c)]++;
    int mx = 0;
    for (auto x: cnt) mx = max(mx, x);
    int p = 0;
    int a = -1, b = -1;
    for (int i = 0; i<3; i++) {
        if (cnt[i] == mx){
            p = i;
        }
    }
    for (int i = 0; i<3; i++){
        if (i == p) continue;
        if (a == -1) a = i;
        else b = i;
    }
    debug(p, a, b);
    s = "$" + s;
    vector<vector<int>>pos(3, {-oo});
    for (int i = 1; i<=n; i++){
        pos[ti(s[i])].emplace_back(i);
    }
    int dp[n+1][cnt[a]+1][cnt[b]+1][3];
    for (int i = 0; i<=n; i++){
        for (int A = 0; A <= cnt[a]; A++){
            for (int B = 0; B <= cnt[b]; B++){
                for (int last = 0; last < 3; last++){
                    dp[i][A][B][last] = oo;
                }
            }
        }
    }
    auto ile = [&](int l, int r, int where){
        int x = (int)(upper_bound(pos[where].begin(), pos[where].end(), r) - upper_bound(pos[where].begin(), pos[where].end(), l));
        return max(0, x);
    };
    //opt -- szukanie ile() nie zalezy od wartosci i, tylko od A, B, C
    //preprocess [now, A], [now, B], [now, C] dla kazdego now \in [1, n] oraz sensownego A, B, C
    vector pre(n+1, vector<vector<int>>(3));
    for (int now = 1; now <= n; now++){
        for (int rep = 0; rep < 3; rep++){
            pre[now][rep].resize(cnt[rep]+1);
            for (int i = 1; i<=cnt[rep]; i++){
                pre[now][rep][i] = ile(now, pos[rep][i], rep);
            }
        }
    }

    for (int i = 0; i<3; i++) dp[0][0][0][i] = 0;
    for (int i = 1; i<=n; i++){
        for (int A = 0; A <= cnt[a]; A++){
            for (int B = 0; B <= min(cnt[b], i-A); B++){
                int C = i - A - B;
                if (C < 0 || C > cnt[p]) continue;
                for (int last = 0; last < 3; last++){
                    for (int prev = 0; prev < 3; prev++){
                        if (last == prev) continue;
                        if (last == a){
                            if (!A) continue;
                            int now = pos[last][A];
                            int cost = now-i + pre[now][b][B] + pre[now][p][C];
                            ckmin(dp[i][A][B][last], dp[i-1][A-1][B][prev] + cost);
                        } else if (last == b){
                            if (!B) continue;
                            int now = pos[last][B];
                            int cost = now-i + pre[now][a][A] + pre[now][p][C];
                            ckmin(dp[i][A][B][last], dp[i-1][A][B-1][prev] + cost);
                        } else {
                            if (!C) continue;
                            int now = pos[p][C];
                            int cost = now-i + pre[now][b][B] + pre[now][a][A];
                            ckmin(dp[i][A][B][last], dp[i-1][A][B][prev] + cost);
                        }
                    }
                }
            }
        }
    }
    int ans = oo;
    for (int last = 0; last < 3; last++){
        ans = min(ans, dp[n][cnt[a]][cnt[b]][last]);
    }
    if (ans == oo) cout << "-1\n";
    else cout << ans << "\n";
}
 
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
 
    return 0;
}

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