Submission #1043005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043005		SoulKnight	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	399 ms	129620 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'


const int INF = 1e9;

struct Seg{
    int n;
    vector<int> seg;

    void init(int n_){
        n = n_;
        seg.assign(2*n, 0);
    }

    void upd(int p, int delta){
        for (seg[p += n] += delta; p > 1; p /= 2) seg[p/2] = seg[p] + seg[p^1];
    }

    int sum(int l, int r){
        int res = 0;
        for (l += n, r += n+1; l < r; l /= 2, r /= 2){
            if (l & 1) res += seg[l++];
            if (r & 1) res += seg[--r];
        }
        return res;
    }
} seg;



int n, sz[3];
string s;
int dp[405][405][405][4];
bool is_set[405][405][405][4];
vector<int> where[3];

int f(array<int, 4>& x){
    // for (int i = 0; i < 4; i++) cout << x[i] << " ";
    // cout << ln;
    if (is_set[x[0]][x[1]][x[2]][x[3]]) return dp[x[0]][x[1]][x[2]][x[3]];

    int ans = INF;
    int old_x3 = x[3];
    for (int i = 0; i < 3; i++){
        if (i == x[3]) continue; // prev moved
        if (x[i] == sz[i]) continue; // already at end

        // use where[i][x[i]]
        seg.upd(where[i][x[i]], 1);
        int t = seg.sum(where[i][x[i]]+1, n-1) + where[i][x[i]] - (x[0] + x[1] + x[2]);

        x[i]++; x[3] = i;

        ans = min(ans, t + (!is_set[x[0]][x[1]][x[2]][x[3]]? f(x): dp[x[0]][x[1]][x[2]][x[3]]));

        x[i]--; x[3] = old_x3;
        seg.upd(where[i][x[i]], -1);
    }

    dp[x[0]][x[1]][x[2]][x[3]] = min(ans, INF); // no overflow
    is_set[x[0]][x[1]][x[2]][x[3]] = 1;

    return dp[x[0]][x[1]][x[2]][x[3]];
}

void solve(){
    cin >> n >> s;
    seg.init(n);

    for (int i = 0; i < n; i++){
        if (s[i] == 'R') where[0].push_back(i);
        if (s[i] == 'G') where[1].push_back(i);
        if (s[i] == 'Y') where[2].push_back(i);
    }
    for (int i = 0; i < 3; i++) sz[i] = where[i].size();
    for (int i = 0; i < 3; i++) is_set[sz[0]][sz[1]][sz[2]][i] = 1;

    array<int, 4> xx = {0, 0, 0, 3};
    int ans = f(xx);
    cout << (ans == INF? -1: ans) << ln;

}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // int TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

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