Submission #3008892

---

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 SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N;
    cin >> N;
    vector<int> a(2 * N);
    vector<char> c(2 * N);
    vector< vector<int> > index(2, vector<int>(N));

    
    REP(i, 2 * N){
        cin >> c[i] >> a[i];
        a[i]--;
        if(c[i] == 'B'){
            index[0][a[i]] = i;
        }else{
            index[1][a[i]] = i;
        }
    }

    //b[i][j]: i番目以降(i番目含まない)のB j未満の数
    //w[i][j]: i番目以降(i番目含まない)のW j未満の数
    vector< vector<int> > b(2 * N, vector<int>(N + 1, 0)), w(2 * N, vector<int>(N + 1, 0));
    REP(j, N + 1){
        int tmpb = j, tmpw = j;
        REP(i, 2 * N){
            if(c[i] == 'B' && a[i] < j){
                tmpb--;
            }else if(c[i] == 'W' && a[i] < j){
                tmpw--;
            }
            b[i][j] = tmpb;
            w[i][j] = tmpw;
        }
    }

    //costb[i][j]: B iより右にある、B 0 ~ B (i-1) と W 0 ~ W (j-1)
    //costw[i][j]: W jより右にある、W 0 ~ W (j-1) と B i ~ B (i-1)
    vector< vector<int> > costb(N, vector<int>(N + 1, 0)), costw(N + 1, vector<int>(N, 0));
    REP(i, N){
        REP(j, N + 1){
            costb[i][j] = b[index[0][i]][i] + w[index[0][i]][j];
        }
    }
    REP(i, N + 1){
        REP(j, N){
            costw[i][j] = w[index[1][j]][j] + b[index[1][j]][i];
        }
    }
    
    vector< vector<int> > dp(N + 1, vector<int>(N + 1));

    FOR(i, 1, N + 1){
        dp[i][0] = dp[i - 1][0] + costb[i - 1][0];
        dp[0][i] = dp[0][i - 1] + costw[0][i - 1];
    }
    FOR(i, 1, N + 1){
        FOR(j, 1, N + 1){
            dp[i][j] = min(dp[i - 1][j] + costb[i - 1][j], dp[i][j - 1] + costw[i][j - 1]);
        }
    }

    cout << dp[N][N];
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Submission Info

Judge Result