Submission #2501806

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#include<time.h>
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<(ll)m; i++)
#define FOR(i,n,m) for(long long i=n; i<(ll)m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

ll N = 2020;
ll bit[2020];
void add(ll a, ll w) {
	a++;
	for (ll x = a; x <= N; x += x & -x) bit[x] += w;
}
ll sum(ll a) {
	a++;
	ll ret = 0;
	for (ll x = a; x > 0; x -= x & -x) ret += bit[x];
 return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin>>n;
	vector<ll> a(2*n);
	vector<char> c(2*n);
	REP(i,2*n) cin>>c[i]>>a[i];
	REP(i,2*n) a[i]--;
	ll ans=0;
	vector<bool> aprd_w(n,false);
	vector<bool> aprd_b(n,false);
	for(ll i=2*n-1; i>=0; i--) {
		if(c[i]=='W') {
			aprd_w[a[i]]=true;
			REP(j,a[i]) if(aprd_w[j])ans++;
		} else {
			aprd_b[a[i]]=true;
			REP(j,a[i]) if(aprd_b[j])ans++;
		}
	}
	vector<vector<ll>> cnt(n,vector<ll>(n+1,0));
	for(ll i=2*n-1; i>=0; i--) {
		if(c[i]=='W') {
			add(a[i],1);
		} else {
			REP(j,n+1) {
				if(j>0) cnt[a[i]][j]+=sum(j-1);
				if(j<n) cnt[a[i]][j]+=(n-j)-(sum(2019)-cnt[a[i]][j]);
			}
		}
	}
	vector<vector<ll>> dp(n,vector<ll>(n+1,INF));
	REP(i,n) {	// 黒 i の球までを
		REP(j,n+1) { // 白 j より左にいれる
			if(j>0) dp[i][j]=dp[i][j-1];
			if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+cnt[i][j]);
			else dp[i][j]=min(dp[i][j],cnt[i][j]);
		}
	}
	ll tmp=INF*INF;
	REP(i,n+1) tmp=min(tmp,dp[n-1][i]);
	cout<<ans+tmp<<endl;
}

Submission Info

Judge Result