Submission #4014062
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-48);
}
int n, p[2][2005], c[2][2005][2005], f[2005][2005], tr[2][4005];
void inc(int col, int p) {for (; p <= (n<<1); p += (p&-p)) tr[col][p]++;}
int sum(int col, int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[col][p]; return ret;}
int main() {
read(n);
for (int i = 1, col, val; i <= (n<<1); i++)
col = getchar() == 'B', read(val), p[col][val] = i;
memset(tr[0], 0, sizeof tr[0]);
for (int i = 1; i <= n; i++) {
memset(tr[1], 0, sizeof tr[1]);
c[0][i][0] = i-1-sum(0, p[0][i]);
for (int j = 1; j <= n; j++)
inc(1, p[1][j]),
c[0][i][j] += i-1-sum(0, p[0][i]),
c[0][i][j] += j-sum(1, p[0][i]);
inc(0, p[0][i]);
}
memset(tr[1], 0, sizeof tr[1]);
for (int j = 1; j <= n; j++) {
memset(tr[0], 0, sizeof tr[0]);
c[1][0][j] = j-1-sum(1, p[1][j]);
for (int i = 1; i <= n; i++)
inc(0, p[0][i]),
c[1][i][j] += j-1-sum(1, p[1][j]),
c[1][i][j] += i-sum(0, p[1][j]);
inc(1, p[1][j]);
}
memset(f, 0x3f, sizeof f), f[0][0] = 0;
for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) {
if (i) f[i][j] = min(f[i][j], f[i-1][j]+c[0][i][j]);
if (j) f[i][j] = min(f[i][j], f[i][j-1]+c[1][i][j]);
}
return printf("%d\n", f[n][n]), 0;
}
Submission Info
Submission Time |
|
Task |
E - Sorted and Sorted |
User |
Azrael_Death |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1457 Byte |
Status |
AC |
Exec Time |
232 ms |
Memory |
47360 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 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 |
7 ms |
18688 KB |
0_001.txt |
AC |
7 ms |
18688 KB |
0_002.txt |
AC |
7 ms |
18688 KB |
1_003.txt |
AC |
7 ms |
18688 KB |
1_004.txt |
AC |
7 ms |
18688 KB |
1_005.txt |
AC |
7 ms |
18688 KB |
1_006.txt |
AC |
7 ms |
18688 KB |
1_007.txt |
AC |
7 ms |
18688 KB |
1_008.txt |
AC |
7 ms |
18688 KB |
1_009.txt |
AC |
7 ms |
18688 KB |
1_010.txt |
AC |
7 ms |
18688 KB |
1_011.txt |
AC |
7 ms |
18688 KB |
1_012.txt |
AC |
7 ms |
18688 KB |
1_013.txt |
AC |
7 ms |
18688 KB |
1_014.txt |
AC |
183 ms |
47360 KB |
1_015.txt |
AC |
31 ms |
28928 KB |
1_016.txt |
AC |
140 ms |
43264 KB |
1_017.txt |
AC |
58 ms |
35072 KB |
1_018.txt |
AC |
8 ms |
20736 KB |
1_019.txt |
AC |
24 ms |
26880 KB |
1_020.txt |
AC |
158 ms |
43264 KB |
1_021.txt |
AC |
52 ms |
35072 KB |
1_022.txt |
AC |
28 ms |
30976 KB |
1_023.txt |
AC |
105 ms |
43264 KB |
1_024.txt |
AC |
157 ms |
47360 KB |
1_025.txt |
AC |
229 ms |
47360 KB |
1_026.txt |
AC |
231 ms |
47360 KB |
1_027.txt |
AC |
224 ms |
47360 KB |
1_028.txt |
AC |
232 ms |
47360 KB |
1_029.txt |
AC |
232 ms |
47360 KB |
1_030.txt |
AC |
227 ms |
47360 KB |
1_031.txt |
AC |
231 ms |
47360 KB |
1_032.txt |
AC |
177 ms |
47360 KB |
1_033.txt |
AC |
166 ms |
47360 KB |
1_034.txt |
AC |
171 ms |
47360 KB |
1_035.txt |
AC |
175 ms |
47360 KB |