Submission #2560242


Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
 
const int maxn=2e3+10,maxn2=2*2e3+10;
int n,a[maxn2],dp[maxn][maxn],rnkw[maxn],rnkb[maxn];
int bit[maxn2];
char c[maxn2][2];
 
inline void add(int pos,int val){
	while(pos<maxn2){
		bit[pos]+=val;
		pos+=pos&-pos;
	}
}
inline int sum(int pos){
	int res=0;
	while(pos){
		res+=bit[pos];
		pos-=pos&-pos;
	}
	return res;
}
inline void chkmin(int&a,int b){
	if(a>b)a=b;
}
 
int main(){
	cin>>n;
	for(int i=1;i<=2*n;++i){
		cin>>c[i]>>a[i];
		if(c[i][0]=='W')
			rnkw[a[i]]=i;
		else
			rnkb[a[i]]=i;
	}
	for(int i=0;i<=n;++i)
		for(int j=0;j<=n;++j)
			dp[i][j]=1e9;
	dp[0][0]=0;
	for(int i=1;i<=n;++i)
		add(rnkw[i],1);
	for(int i=0;i<=n;++i){
		if(i)
			add(rnkw[i],-1);
		for(int j=1;j<=n;++j)
			add(rnkb[j],1);
		for(int j=0;j<=n;++j){
			if(j)
				add(rnkb[j],-1);
			if(i<n)
				chkmin(dp[i+1][j],dp[i][j]+sum(rnkw[i+1])-1);
			if(j<n)
				chkmin(dp[i][j+1],dp[i][j]+sum(rnkb[j+1])-1);
		}
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

Submission Info

Submission Time
Task E - Sorted and Sorted
User tyclear
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1108 Byte
Status AC
Exec Time 191 ms
Memory 16000 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 36
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 256 KB
1_013.txt AC 1 ms 256 KB
1_014.txt AC 149 ms 14592 KB
1_015.txt AC 23 ms 6144 KB
1_016.txt AC 111 ms 12544 KB
1_017.txt AC 47 ms 8448 KB
1_018.txt AC 2 ms 768 KB
1_019.txt AC 17 ms 6016 KB
1_020.txt AC 129 ms 14592 KB
1_021.txt AC 34 ms 8448 KB
1_022.txt AC 18 ms 6144 KB
1_023.txt AC 73 ms 12544 KB
1_024.txt AC 106 ms 15744 KB
1_025.txt AC 189 ms 16000 KB
1_026.txt AC 189 ms 16000 KB
1_027.txt AC 191 ms 16000 KB
1_028.txt AC 190 ms 16000 KB
1_029.txt AC 190 ms 16000 KB
1_030.txt AC 189 ms 16000 KB
1_031.txt AC 190 ms 16000 KB
1_032.txt AC 116 ms 16000 KB
1_033.txt AC 107 ms 16000 KB
1_034.txt AC 122 ms 16000 KB
1_035.txt AC 110 ms 16000 KB