Submission #762098

#	Time	Username	Problem	Language	Result	Execution time	Memory
762098		sysia	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	1095 ms	149720 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 = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

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++){
        int x = ti(s[i]);
        pos[x].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(0ll, x);
    };
    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;
                            if (B) cost += ile(now, pos[b][B], b);
                            if (C) cost += ile(now, pos[p][C], p);
                            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;
                            if (A) cost += ile(now, pos[a][A], a);
                            if (C) cost += ile(now, pos[p][C], p);
                            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;
                            if (A) cost += ile(now, pos[a][A], a);
                            if (B) cost += ile(now, pos[b][B], b);
                            ckmin(dp[i][A][B][last], dp[i-1][A][B][prev] + cost);
                        }
                    }
                    if (dp[i][A][B][last] >= oo) continue;
                }
            }
        }
    }
    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);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

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