Submission #1150160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150160		Shadow1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	269 ms	380884 KiB

joi2019_ho_t3

// Programmer: Shadow1

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!

#define i64 int64_t
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define prq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());

// 
const int INF = 1e15;
void solve() {
    int n; str s;
    cin >> n >> s;
    int cr = 0, cg = 0, cy = 0;
    for(auto &S : s) {
        cr += (S == 'R');
        cg += (S == 'G');
        cy += (S == 'Y');
    }
    if(cr > (n+1)/2 || cg > (n+1)/2 || cy > (n+1)/2) {
        cout << -1 << '\n';
        return;
    }
    int dp[n+1][cr+1][cg+1][3];
    vector<int> r, g, y;
    for(int i=0; i<n; ++i) {
        if(s[i] == 'R')
            r.push_back(i+1);
        else if(s[i] == 'G')
            g.push_back(i+1);
        else
            y.push_back(i+1);
    }
    for(int i=0; i<=n; ++i) {
        for(int j=0; j<=cr; ++j) {
            for(int k=0; k<=cg; ++k) {
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = INF;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for(int i=1; i<=n; ++i) {
        for(int j=0; j<=cr; ++j) {
            for(int k=0; k<=cg; ++k) {
                int l = i - j - k;
                if(j > 0)
                    dp[i][j][k][0] = min(dp[i-1][j-1][k][1], dp[i-1][j-1][k][2]) +  abs(r[j-1] - i); // place a 'R'
                if(k > 0)
                    dp[i][j][k][1] = min(dp[i-1][j][k-1][0], dp[i-1][j][k-1][2]) + abs(g[k-1] - i);  // place a 'G'
                if(l > 0 && l <= cy)
                    dp[i][j][k][2] = min(dp[i-1][j][k][0], dp[i-1][j][k][1]) + abs(y[l-1] - i); // place a 'Y'
            }
        }
    }
    int ans = min({dp[n][cr][cg][0], dp[n][cr][cg][1], dp[n][cr][cg][2]}) / 2;
    cout << (ans == INF ? -1 : ans) << '\n';

}



// CHECK YOUR OVERFLOWS!!!! 
signed main() {
    // freopen("output.txt", "w", stdout);
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    int T = 1;
    // cin >> T;
    

    for(int tc = 1; tc <= T; ++tc) {
        // cout << "Case #" << tc << ": ";
        solve();
    }

    return 0;
}

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