Submission #2502904

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

template<typename T, typename S>
istream& operator>> (istream& in, pair<S, T>& p) {
    in >> p.fs >> p.sn;
    return in;
}
template<typename T, typename S>
ostream& operator<< (ostream& out, pair<S, T>& p) {
    out << p.fs << ' ' << p.sn << ' ';
    return out;
}

template<typename T>
istream& operator>> (istream& in, vector<T>& v) {
    for (T& x : v) in >> x;
    return in;
}
template<typename T>
ostream& operator<< (ostream& out, vector<T>& v) {
    for (T& x : v) out << x << ' ';
    return out;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 2018;
int w[N][2 * N], b[N][2 * N];
int posw[N], posb[N];
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    forn(i, 0, 2 * n) {
        char c;
        int val;
        cin >> c >> val;
        (c == 'B' ? posb : posw)[--val] = i;
    }
    forn(i, 0, n) {
        if (i) {
            forn(j, 0, 2 * n) w[i][j] = w[i - 1][j];
            forn(j, 0, 2 * n) b[i][j] = b[i - 1][j];
        }
        forn(j, posw[i], 2 * n) ++w[i][j];
        forn(j, posb[i], 2 * n) ++b[i][j];
    }
    fore(i, 0, n)
        fore(j, 0, n) {
            if (i == 0 && j == 0) continue;
            dp[i][j] = INF;
            if (i) {
                --i, --j;
                int lftI = posw[i] - (i ? w[i - 1][posw[i]] : 0) - (j == -1 ? 0 : b[j][posw[i]]);
                ++i, ++j;
                setmin(dp[i][j], dp[i - 1][j] + lftI);
            }
            if (j) {
                --i, --j;
                int lftJ = posb[j] - (j ? b[j - 1][posb[j]] : 0) - (i == -1 ? 0 : w[i][posb[j]]);
                ++i, ++j;
                setmin(dp[i][j], dp[i][j - 1] + lftJ);
            }
        }
    //fore(i, 0, n) {
    //    fore(j, 0, n) cerr << dp[i][j] << ' ';
    //    cerr << '\n';
    //}
    cout << dp[n][n] << '\n';
}

Submission Info

Judge Result