Submission #3422131

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define IFOR(k,a,b) for(int k=(a); k>=(b); --k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define IREP(k,a) for(int k=a-1; k>=(0);--k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define x first
#define y second
#define INF 1000000001
#define INFLONG 1000000000000000000
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define MAXM 200000
#define MAXN 1000000
#define PI 3.1415926535897932384626
#define ERR -987654321
#define MEM(a,b) memset(a,b,sizeof(a));
#define read1(a) scanf("%d",&a)
#define read2(a,b) scanf("%d%d",&a,&b)
#define read3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define readl1(a) scanf("%lld",&a)
#define readl2(a,b) scanf("%lld%lld",&a,&b)
#define readl3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int rn = uniform_int_distribution<int>(0, MAXN)(rng);

    int n,x,y;
    char s;
    cin>>n;
    pii a[2*n];
    int b[2][n+1][n+1] , z[2][n+1];
    MEM(b,0); MEM(z,0);

    REP(i,2*n) {
        cin>>s>>y;
        if(s == 'W') x = 0;
        else x = 1;
        a[i] = MP(x,y);
    }

    REP(i,2*n) {
        REP(j,i) {
            if(a[j].x == a[i].x && a[j].y > a[i].y) z[a[i].x][a[i].y] += 1;
            else if(a[j].x != a[i].x) {
                b[a[i].x][a[i].y][a[j].y] += 1;
            }
        }
        REP(j,n+1) if(j) b[a[i].x][a[i].y][j] += b[a[i].x][a[i].y][j-1];
    }

    int dp[n][n];
    dp[0][0] = 0;
    FOR(i,1,n) dp[i][0] = dp[i-1][0] + z[0][i] + b[0][i][n];
    FOR(j,1,n) dp[0][j] = dp[0][j-1] + z[1][j] + b[1][j][n];
    
    FOR(i,1,n) {
        FOR(j,1,n) {
            int p = dp[i-1][j] + z[0][i] + b[0][i][n] - b[0][i][j];
            int q = dp[i][j-1] + z[1][j] + b[1][j][n] - b[1][j][i];
            dp[i][j] = min(p, q);
        }
    }
    
    cout<<dp[n][n];
    return 0;
}

Submission Info

Judge Result