Submission #8430297

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int dp[2010][2010];
int p[2][2010];
int sum[2][4010][2010];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	int a; char c;
	for(int i=0;i<2*n;i++){
		cin >> c >> a;
		if(c=='W'){
			p[0][a-1]=i;
			sum[0][i][a-1]=1;
		}
		else{
			p[1][a-1]=i;
			sum[1][i][a-1]=1;
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=1e9;
		}
	}
	for(int k=0;k<2;k++){
		for(int i=0;i<2*n;i++){
			for(int j=n-1;j>=1;j--){
				sum[k][i][j-1]+=sum[k][i][j];
			}
		}
		for(int i=0;i<2*n-1;i++){
			for(int j=0;j<n;j++){
				sum[k][i+1][j]+=sum[k][i][j];
			}
		}
	}
	dp[0][0]=0;
	for(int i=0;i<n+1;i++){
		for(int j=0;j<n+1;j++){
			if(i<n){
				int pp=p[0][i];
				dp[i+1][j]=min(dp[i+1][j],dp[i][j]+sum[0][pp][i+1]+sum[1][pp][j]);
			}
			if(j<n){
				int pp=p[1][j];
				dp[i][j+1]=min(dp[i][j+1],dp[i][j]+sum[0][pp][i]+sum[1][pp][j+1]);
			}
		}
	}
	cout << dp[n][n] << endl;
}

Submission Info

Judge Result