Submission #8384669

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

int dp[2001][2001];
int B[2001][2001];
int W[2001][2001];

int main(){
    int n;
    cin >> n;
    vector<int>a(2*n);
    vector<char>c(2*n);
    vector<int>ib(n+1);
    vector<int>iw(n+1);
    rep(i,2*n){
        cin >> c[i] >> a[i];
        if(c[i]=='B'){
            ib[a[i]] = i;
        }else{
            iw[a[i]] = i;
        }
    }
    for(int i=1;i<=n;i++){
        int bid = ib[i];
        int cnt = 0;
        for(int j=0;j<bid;j++){
            if(c[j]=='B'){
                if(a[j]>i){
                    cnt++;
                }
            }else{
                B[i][a[j]-1]++;
            }
        }
        for(int j=n-1;j>=0;j--){
            B[i][j] += B[i][j+1];
        }
        for(int j=n;j>=0;j--){
            B[i][j] += cnt;
        }
    }
    for(int i=1;i<=n;i++){
        int wid = iw[i];
        int cnt = 0;
        for(int j=0;j<wid;j++){
            if(c[j]=='W'){
                if(a[j]>i){
                    cnt++;
                }
            }else{
                W[i][a[j]-1]++;
            }
        }
        for(int j=n-1;j>=0;j--){
            W[i][j] += W[i][j+1];
        }
        for(int j=n;j>=0;j--){
            W[i][j] += cnt;
        }
    }
    // rep(i,n+1){
    //     rep(j,n+1){
    //         cerr << "i:" << i << " j:" << j << " " << B[i][j] << endl;  
    //     }
    // }
    // rep(i,n+1){
    //     rep(j,n+1){
    //         cerr << "i:" << i << " j:" << j << " " << W[i][j] << endl;  
    //     }
    // }
    rep(i,n+1){
        rep(j,n+1){
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i!=0){
                dp[i][j] = min(dp[i][j],dp[i-1][j] + B[i][j]);
            }
            if(j!=0){
                dp[i][j] = min(dp[i][j],dp[i][j-1] + W[j][i]);
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

Submission Info

Judge Result