Submission #8449117
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
const int N=4005;
char c[N];
int a[N],tree[2][N],cntb[N][N],cntw[N][N],ind[2][N];
int dp[N][N];
int prev(int x)
{
return (x&(x-1));
}
int next(int x)
{
return 2*x-prev(x);
}
void update(int type, int ind, int diff)
{
while(ind<=2*N)
{
tree[type][ind]+=diff;
ind=next(ind);
}
}
int get(int type, int ind1, int ind2)
{
int ans=0;
while(ind2)
{
ans+=tree[type][ind2];
ind2=prev(ind2);
}
ind1--;
while(ind1)
{
ans-=tree[type][ind1];
ind1=prev(ind1);
}
return ans;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=2*n;i++)
{
cin>>c[i]>>a[i];
ind[c[i]=='W'][a[i]]=i;
}
for(int i=0;i<n;i++)
{
cntb[i][0]=get(0,ind[0][i+1]+1,2*n);
for(int j=1;j<=n;j++)
{
update(1,ind[1][j],1);
cntb[i][j]=get(1,ind[0][i+1]+1,2*n)+cntb[i][0];
}
for(int j=1;j<=n;j++)
update(1,ind[1][j],-1);
update(0,ind[0][i+1],1);
}
for(int i=0;i<n;i++)
update(0,ind[0][i+1],-1);
for(int i=0;i<n;i++)
{
cntw[i][0]=get(1,ind[1][i+1]+1,2*n);
for(int j=1;j<=n;j++)
{
update(0,ind[0][j],1);
cntw[i][j]=get(0,ind[1][i+1]+1,2*n)+cntw[i][0];
}
for(int j=1;j<=n;j++)
update(0,ind[0][j],-1);
update(1,ind[1][i+1],1);
}
/*cout<<"Cntb: "<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<=n;j++)
cout<<i<<" "<<j<<" "<<cntb[i][j]<<endl;
cout<<endl;
}
cout<<endl;
cout<<"Cntw: "<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<=n;j++)
cout<<i<<" "<<j<<" "<<cntw[i][j]<<endl;
cout<<endl;
}
cout<<endl;*/
dp[0][0]=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 && j==0) continue;
if(i==0)
dp[i][j]=dp[i][j-1]+cntw[j-1][i];
else if(j==0)
dp[i][j]=dp[i-1][j]+cntb[i-1][j];
else
dp[i][j]=min(dp[i-1][j]+cntb[i-1][j],dp[i][j-1]+cntw[j-1][i]);
}
}
/*cout<<"Dp:"<<endl;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
cout<<endl;
}
cout<<endl;*/
cout<<dp[n][n]<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Sorted and Sorted |
User |
lukasanarski |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2544 Byte |
Status |
WA |
Exec Time |
390 ms |
Memory |
98048 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 600 |
Status |
|
|
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 |
2 ms |
4352 KB |
0_001.txt |
AC |
2 ms |
4352 KB |
0_002.txt |
AC |
2 ms |
4352 KB |
1_003.txt |
AC |
2 ms |
4352 KB |
1_004.txt |
AC |
2 ms |
4352 KB |
1_005.txt |
AC |
2 ms |
4352 KB |
1_006.txt |
AC |
2 ms |
4352 KB |
1_007.txt |
AC |
2 ms |
4352 KB |
1_008.txt |
AC |
2 ms |
4352 KB |
1_009.txt |
AC |
2 ms |
4352 KB |
1_010.txt |
AC |
2 ms |
4352 KB |
1_011.txt |
AC |
2 ms |
4352 KB |
1_012.txt |
AC |
2 ms |
4352 KB |
1_013.txt |
AC |
2 ms |
4352 KB |
1_014.txt |
WA |
308 ms |
87680 KB |
1_015.txt |
WA |
48 ms |
35968 KB |
1_016.txt |
AC |
237 ms |
75264 KB |
1_017.txt |
AC |
97 ms |
50432 KB |
1_018.txt |
WA |
3 ms |
6912 KB |
1_019.txt |
AC |
35 ms |
29824 KB |
1_020.txt |
AC |
262 ms |
81536 KB |
1_021.txt |
AC |
82 ms |
52608 KB |
1_022.txt |
AC |
47 ms |
38016 KB |
1_023.txt |
WA |
188 ms |
75392 KB |
1_024.txt |
AC |
280 ms |
96000 KB |
1_025.txt |
WA |
389 ms |
98048 KB |
1_026.txt |
WA |
389 ms |
98048 KB |
1_027.txt |
WA |
389 ms |
98048 KB |
1_028.txt |
WA |
389 ms |
98048 KB |
1_029.txt |
WA |
390 ms |
98048 KB |
1_030.txt |
WA |
389 ms |
98048 KB |
1_031.txt |
WA |
389 ms |
98048 KB |
1_032.txt |
AC |
291 ms |
98048 KB |
1_033.txt |
AC |
285 ms |
98048 KB |
1_034.txt |
WA |
289 ms |
98048 KB |
1_035.txt |
AC |
285 ms |
98048 KB |