Submission #3934513

---

Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}



signed main(){

    int N; cin >> N;
    vector<char> c(2 * N);
    vec a(2 * N);
    REP(i, 2 * N){
        cin >> c[i] >> a[i];
        a[i]--;
    }

    mat inv(2, vec(N));
    REP(i, 2 * N){
        if(c[i] == 'W') inv[0][a[i]] = i;
        else inv[1][a[i]] = i;
    }

    mat B(N + 1, vec(2 * N + 1, 0)), W(N + 1, vec(2 * N + 1, 0));
    REP(i, N) FOR(j, inv[0][i] + 1, 2 * N + 1) W[i + 1][j] = 1;
    REP(j, 2 * N + 1) FOR(i, 1, N + 1) W[i][j] += W[i - 1][j];
    REP(i, N) FOR(j, inv[1][i] + 1, 2 * N + 1) B[i + 1][j] = 1;
    REP(j, 2 * N + 1) FOR(i, 1, N + 1) B[i][j] += B[i - 1][j];

    mat dp(2 * N + 1, vec(N + 1, INF));
    dp[0][0] = 0;
    FOR(i, 1, 2 * N + 1){
        REP(j, min(i, N) + 1){
            int v1 = INF, v2 = INF;
            int nW = i - j, nB = j;
            if(nW > N) continue;
            //W置いた
            if(nW >= 1) v1 = dp[i - 1][j] + nW - 1 + nB - W[nW - 1][inv[0][nW - 1]] - B[nB][inv[0][nW - 1]];
            //B置いた
            if(nB >= 1) v2 = dp[i - 1][j - 1] + nB - 1 + nW - B[nB - 1][inv[1][nB - 1]] - W[nW][inv[1][nB - 1]];

            dp[i][j] = min(v1, v2);
        }
    }
    cout << dp[2 * N][N] << endl;
    
    return 0;
}

Submission Info

Judge Result