Submission #3727126
Source Code Expand
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
int solve(int n, vector<char> const & c, vector<int> const & a) {
auto delta_w = vectors(n + 1, n + 1, int());
REP (w, n + 1) {
REP (i, 2 * n) {
if (c[i] == 'B') {
delta_w[w][0] += 1;
delta_w[w][a[i] + 1] -= 1;
} else {
if (a[i] == w) break;
delta_w[w][0] += (a[i] >= w);
}
}
REP (b, n) {
delta_w[w][b + 1] += delta_w[w][b];
}
}
auto delta_b = vectors(n + 1, n + 1, int());
REP (b, n + 1) {
REP (i, 2 * n) {
if (c[i] == 'B') {
if (a[i] == b) break;
delta_b[0][b] += (a[i] >= b);
} else {
delta_b[0][b] += 1;
delta_b[a[i] + 1][b] -= 1;
}
}
REP (w, n) {
delta_b[w + 1][b] += delta_b[w][b];
}
}
auto dp = vectors(n + 1, n + 1, INT_MAX);
dp[0][0] = 0;
REP (w, n + 1) {
REP (b, n + 1) {
if (w - 1 >= 0) {
chmin(dp[w][b], dp[w - 1][b] + delta_w[w - 1][b]);
}
if (b - 1 >= 0) {
chmin(dp[w][b], dp[w][b - 1] + delta_b[w][b - 1]);
}
}
}
return dp[n][n];
}
int main() {
int n; cin >> n;
vector<char> c(2 * n);
vector<int> a(2 * n);
REP (i, 2 * n) {
cin >> c[i] >> a[i];
-- a[i];
}
cout << solve(n, c, a) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Sorted and Sorted |
User |
kimiyuki |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
1946 Byte |
Status |
AC |
Exec Time |
142 ms |
Memory |
47488 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 |
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 |
AC |
105 ms |
37120 KB |
1_015.txt |
AC |
10 ms |
5632 KB |
1_016.txt |
AC |
78 ms |
27648 KB |
1_017.txt |
AC |
29 ms |
11520 KB |
1_018.txt |
AC |
2 ms |
384 KB |
1_019.txt |
AC |
7 ms |
3968 KB |
1_020.txt |
AC |
93 ms |
32256 KB |
1_021.txt |
AC |
31 ms |
12800 KB |
1_022.txt |
AC |
12 ms |
6784 KB |
1_023.txt |
AC |
77 ms |
27904 KB |
1_024.txt |
AC |
120 ms |
45696 KB |
1_025.txt |
AC |
141 ms |
47360 KB |
1_026.txt |
AC |
140 ms |
47360 KB |
1_027.txt |
AC |
142 ms |
47360 KB |
1_028.txt |
AC |
141 ms |
47360 KB |
1_029.txt |
AC |
139 ms |
47360 KB |
1_030.txt |
AC |
141 ms |
47488 KB |
1_031.txt |
AC |
139 ms |
47360 KB |
1_032.txt |
AC |
116 ms |
47360 KB |
1_033.txt |
AC |
136 ms |
47360 KB |
1_034.txt |
AC |
132 ms |
47360 KB |
1_035.txt |
AC |
127 ms |
47360 KB |