Submission #3008871


Source Code Expand

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N;
    cin >> N;
    vector<int> a(2 * N);
    vector<char> c(2 * N);
    vector< vector<int> > index(2, vector<int>(N));

    
    REP(i, 2 * N){
        cin >> c[i] >> a[i];
        a[i]--;
        if(c[i] == 'B'){
            index[0][a[i]] = i;
        }else{
            index[1][a[i]] = i;
        }
    }

    /*
    //b[i][j]: i番目までにある、j未満のBの要素数
    vector< vector<int> > b(2 * N, vector<int>(N + 1, 0)), w(2 * N, vector<int>(N + 1, 0));
    REP(j, N + 1){
        int tmpb = 0, tmpw = 0;
        REP(i, 2 * N){
            if(c[i] == 'B' && a[i] < j){
                tmpb++;
            }else if(c[i] == 'W' && a[i] < j){
                tmpw++;
            }
            b[i][j] = tmpb;
            w[i][j] = tmpw;
        }
    }*/

    //costb[i][j]: B iより右にある、B 0 ~ B (i-1) と W 0 ~ W (j-1)
    //costw[i][j]: W jより右にある、W 0 ~ W (j-1) と B i ~ B (i-1)
    vector< vector<int> > costb(N, vector<int>(N + 1, 0)), costw(N + 1, vector<int>(N, 0));
    REP(i, N){
        REP(j, N + 1){
            FOR(k, index[0][i], 2 * N){
                if(c[k] == 'B' && a[k] < i) costb[i][j]++;
                if(c[k] == 'W' && a[k] < j) costb[i][j]++;
            }
        }
    }
    REP(i, N + 1){
        REP(j, N){
            FOR(k, index[1][j], 2 * N){
                if(c[k] == 'W' && a[k] < j) costw[i][j]++;
                if(c[k] == 'B' && a[k] < i) costw[i][j]++;
            }
        }
    }
    
    vector< vector<int> > dp(N + 1, vector<int>(N + 1));

    FOR(i, 1, N + 1){
        dp[i][0] = dp[i - 1][0] + costb[i - 1][0];
        dp[0][i] = dp[0][i - 1] + costw[0][i - 1];
    }
    FOR(i, 1, N + 1){
        FOR(j, 1, N + 1){
            dp[i][j] = min(dp[i - 1][j] + costb[i - 1][j], dp[i][j - 1] + costw[i][j - 1]);
        }
    }

    cout << dp[N][N];
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Submission Info

Submission Time
Task E - Sorted and Sorted
User sumitacchan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2495 Byte
Status TLE
Exec Time 2108 ms
Memory 65024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 18
TLE × 18
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 TLE 2107 ms 49280 KB
1_015.txt AC 1280 ms 11008 KB
1_016.txt TLE 2106 ms 36736 KB
1_017.txt TLE 2104 ms 15232 KB
1_018.txt AC 6 ms 512 KB
1_019.txt AC 728 ms 7680 KB
1_020.txt TLE 2106 ms 42880 KB
1_021.txt TLE 2105 ms 16896 KB
1_022.txt AC 1480 ms 13312 KB
1_023.txt TLE 2106 ms 39040 KB
1_024.txt TLE 2107 ms 60672 KB
1_025.txt TLE 2108 ms 62976 KB
1_026.txt TLE 2108 ms 62976 KB
1_027.txt TLE 2106 ms 65024 KB
1_028.txt TLE 2108 ms 62976 KB
1_029.txt TLE 2108 ms 62976 KB
1_030.txt TLE 2108 ms 62976 KB
1_031.txt TLE 2108 ms 62976 KB
1_032.txt TLE 2107 ms 65024 KB
1_033.txt TLE 2108 ms 62976 KB
1_034.txt TLE 2108 ms 62976 KB
1_035.txt TLE 2108 ms 62976 KB