Submission #8449126


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const long long N=4005;
char c[N];
long long a[N],tree[2][N],cntb[N][N],cntw[N][N],ind[2][N];
long long dp[N][N];
long long prev(long long x)
{
    return (x&(x-1));
}
long long next(long long x)
{
    return 2*x-prev(x);
}
void update(long long type, long long ind, long long diff)
{
    while(ind<=2*N)
    {
        tree[type][ind]+=diff;
        ind=next(ind);
    }
}
long long get(long long type, long long ind1, long long ind2)
{
    long long 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()
{
    long long n;
    cin>>n;
    for(long long i=1;i<=2*n;i++)
    {
        cin>>c[i]>>a[i];
        ind[c[i]=='W'][a[i]]=i;
    }
    for(long long i=0;i<n;i++)
    {
        cntb[i][0]=get(0,ind[0][i+1]+1,2*n);
        for(long long 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(long long j=1;j<=n;j++)
            update(1,ind[1][j],-1);
        update(0,ind[0][i+1],1);
    }
    for(long long i=0;i<n;i++)
        update(0,ind[0][i+1],-1);
    for(long long i=0;i<n;i++)
    {
        cntw[i][0]=get(1,ind[1][i+1]+1,2*n);
        for(long long 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(long long j=1;j<=n;j++)
            update(0,ind[0][j],-1);
        update(1,ind[1][i+1],1);
    }
    /*cout<<"Cntb: "<<endl;
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<=n;j++)
            cout<<i<<" "<<j<<" "<<cntb[i][j]<<endl;
        cout<<endl;
    }
    cout<<endl;
    cout<<"Cntw: "<<endl;
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<=n;j++)
            cout<<i<<" "<<j<<" "<<cntw[i][j]<<endl;
        cout<<endl;
    }
    cout<<endl;*/
    dp[0][0]=0;
    for(long long i=0;i<=n;i++)
    {
        for(long long 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(long long i=0;i<=n;i++)
    {
        for(long long 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 2736 Byte
Status WA
Exec Time 396 ms
Memory 190080 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 24
WA × 12
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 4480 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 4480 KB
1_007.txt AC 2 ms 4352 KB
1_008.txt AC 2 ms 4480 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 314 ms 171520 KB
1_015.txt WA 53 ms 66432 KB
1_016.txt AC 244 ms 146816 KB
1_017.txt AC 103 ms 95232 KB
1_018.txt WA 4 ms 10880 KB
1_019.txt AC 39 ms 54144 KB
1_020.txt AC 270 ms 159104 KB
1_021.txt AC 89 ms 99456 KB
1_022.txt AC 52 ms 72576 KB
1_023.txt WA 195 ms 146816 KB
1_024.txt AC 289 ms 188032 KB
1_025.txt WA 395 ms 190080 KB
1_026.txt WA 396 ms 190080 KB
1_027.txt WA 394 ms 190080 KB
1_028.txt WA 396 ms 190080 KB
1_029.txt WA 396 ms 190080 KB
1_030.txt WA 394 ms 190080 KB
1_031.txt WA 394 ms 190080 KB
1_032.txt AC 300 ms 190080 KB
1_033.txt AC 291 ms 189952 KB
1_034.txt WA 297 ms 190080 KB
1_035.txt AC 294 ms 190080 KB