Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.7 kB
3
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

int n;
vector<pair<int, int>> balls;
vector<vector<int>> precalc;
vector<int> pw, pb;
map<int, int> wp, bp;

void solve(int i, int j) {
    if (i < n && precalc[i + 1][j] == -1) {
        precalc[i + 1][j] = precalc[i][j] + max(0, pb[wp[i + 1] + 1] - pb[i + j]); // ???
        solve(i + 1, j);
    }
    if (j < n && precalc[i][j + 1] == -1) {
        precalc[i][j + 1] = precalc[i][j] + max(0, pw[bp[j + 1] + 1] - pw[i + j]); // ???
        solve(i, j + 1);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    precalc.assign(n + 1, vector<int> (n + 1, -1));
    precalc[0][0] = 0;
    pw.assign(2 * n + 1, 0);
    pb.assign(2 * n + 1, 0);
    int inv = 0;
    for (int i = 0; i < 2 * n; i++) {
        pw[i + 1] = pw[i];
        pb[i + 1] = pb[i];
        char t;
        int v;
        cin >> t >> v;
        if (t == 'W') {
            balls.emplace_back(v, 0);
            for (int j = 0; j < i; j++) {
                if (balls[j].second == 0 && balls[j].first > v) {
                    inv++;
                }
            }
            wp[v] = i;
            pw[i + 1]++;
        } else {
            balls.emplace_back(v, 1);
            for (int j = 0; j < i; j++) {
                if (balls[j].second == 1 && balls[j].first > v) {
                    inv++;
                }
            }
            bp[v] = i;
            pb[i + 1]++;
        }
    }
    solve(0, 0);
    cout << inv + precalc[n][n];
    return 0;
}