Submission #8506171


Source Code Expand

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

int n, a[4003][2], b[2003][2], c[4003][2003][2], dp[2003][2003];
char ch;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= 2 * n; ++i) {
		cin >> ch >> a[i][1];
		a[i][0] = ch == 'B' ? 0 : 1;
		b[a[i][1]][a[i][0]] = i;
	}
	for(int i = 2 * n; i >= 1; --i) {
		for(int j = 1; j <= n; ++j) {
			c[i][j][0] = c[i + 1][j][0];
			c[i][j][1] = c[i + 1][j][1];
		}
		++c[i][a[i][1]][a[i][0]];
	}
	for(int i = 1; i <= 2 * n; ++i) {
		for(int j = 2; j <= n; ++j) {
			c[i][j][0] += c[i][j - 1][0];
			c[i][j][1] += c[i][j - 1][1];
		}
	}
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= n; ++j) {
			if(i + j) dp[i][j] = 1e9;
			if(i) {
				dp[i][j] = dp[i - 1][j] + (b[i][0] - (i + j) + (c[b[i][0]][i - 1][0] + c[b[i][0]][j][1]));
			}
			if(j) {
				dp[i][j] = min(dp[i][j], dp[i][j - 1] + (b[j][1] - (i + j) + (c[b[j][1]][i][0] + c[b[j][1]][j - 1][1])));
			}
		}
	}
	cout << dp[n][n] << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Sorted and Sorted
User NachoLibre
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1030 Byte
Status AC
Exec Time 105 ms
Memory 78592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 36
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 2304 KB
0_001.txt AC 1 ms 2304 KB
0_002.txt AC 2 ms 2304 KB
1_003.txt AC 1 ms 2304 KB
1_004.txt AC 2 ms 2304 KB
1_005.txt AC 2 ms 2304 KB
1_006.txt AC 2 ms 2304 KB
1_007.txt AC 2 ms 2304 KB
1_008.txt AC 1 ms 2304 KB
1_009.txt AC 2 ms 2304 KB
1_010.txt AC 1 ms 2304 KB
1_011.txt AC 1 ms 2304 KB
1_012.txt AC 1 ms 2304 KB
1_013.txt AC 1 ms 2304 KB
1_014.txt AC 75 ms 71936 KB
1_015.txt AC 13 ms 28672 KB
1_016.txt AC 56 ms 61696 KB
1_017.txt AC 23 ms 41216 KB
1_018.txt AC 2 ms 6912 KB
1_019.txt AC 10 ms 26496 KB
1_020.txt AC 65 ms 67840 KB
1_021.txt AC 25 ms 43264 KB
1_022.txt AC 14 ms 30720 KB
1_023.txt AC 64 ms 63744 KB
1_024.txt AC 82 ms 78080 KB
1_025.txt AC 94 ms 78592 KB
1_026.txt AC 93 ms 78592 KB
1_027.txt AC 94 ms 78592 KB
1_028.txt AC 93 ms 78592 KB
1_029.txt AC 95 ms 78592 KB
1_030.txt AC 94 ms 78592 KB
1_031.txt AC 94 ms 78592 KB
1_032.txt AC 98 ms 78592 KB
1_033.txt AC 101 ms 78592 KB
1_034.txt AC 105 ms 78592 KB
1_035.txt AC 85 ms 78592 KB