Untitled
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; }