Submission #8385476

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 2005;

ll dp[MAX_N][MAX_N];
P prv[MAX_N][MAX_N];
int black[2*MAX_N][MAX_N], white[2*MAX_N][MAX_N];

template<typename T> class BIT {
private:
	int n;
	vector<T> bit;
public:
	// 0_indexed で i 番目の要素に x を加える
	void add(int i, T x){
		i++;
		while(i < n){
			bit[i] += x, i += i & -i;
		}
	}
	// 0_indexed で [0,i] の要素の和(両閉区間！！)
	T sum(int i){
		i++;
		T s = 0;
		while(i > 0){
			s += bit[i], i -= i & -i;
		}
		return s;
	}
	BIT(){}
	//初期値がすべて0の場合
	BIT(int sz) : n(sz+1), bit(n, 0){}
	BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
		for(int i = 0; i < n-1; i++){
			add(i,v[i]);
		}
	}
	void print(){
		for(int i = 0; i < n-1; i++){
			cout << sum(i) - sum(i-1) << " ";
		}
		cout << "\n";
	}
	//-1スタート
	void print_sum(){
		for(int i = 0; i < n; i++){
			cout << sum(i-1) << " ";
		}
		cout << "\n";
	}
};
long long inv_count(const vector<int>& u)
{
	int n = (int)u.size();
	BIT<int> bt(n);
	long long ans = 0;
	for(int i = 0; i < n; i++){
		ans += i - bt.sum(u[i]);
		bt.add(u[i], 1);
	}
	return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i,n+1){
        rep(j,n+1){
            dp[i][j] = (1LL << 60);
        }
    }
    vector<int> u, v, p(n), q(n), val(2*n);
    vector<char> c(2*n);
    rep(i,2*n){
        cin >> c[i] >> val[i];
        --val[i];
    }
    rep(i,2*n){
        if(c[i] == 'B'){
            u.pb(val[i]), p[val[i]] = i;
            rep(j,i){
                if(c[j] == 'W'){
                    ++black[i][val[j]];
                }
            }
            rrep(j,n){
                black[i][j] += black[i][j+1];
            }
        }else{
            v.pb(val[i]), q[val[i]] = i;
            rep(j,i){
                if(c[j] == 'B'){
                    ++white[i][val[j]];
                }
            }
            rrep(j,n){
                white[i][j] += white[i][j+1];
            }
        }
    }
    dp[0][0] = 0;
    rep(i,n+1){
        rep(j,n+1){
            if(i < n){
                if(dp[i+1][j] > dp[i][j] + black[p[i]][j]){
                    prv[i+1][j] = P(i, j);
                }
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + black[p[i]][j]);
            }
            if(j < n){
                if(dp[i][j+1] > dp[i][j] + white[q[j]][i]){
                    prv[i][j+1] = P(i, j);
                }
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + white[q[j]][i]);
            }
        }
    }
    cout << dp[n][n] + inv_count(u) + inv_count(v) << "\n";
    return 0;
}

Submission Info

Judge Result