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 |
|
|
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 |