Submission #4012509
Source Code Expand
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
using ll = long long;
#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;
template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp> class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }
//Binary Indexed Tree
class Binary_Indexed_Tree_Range_Sum_Query {
public:
int N;
vector<long long> node;
Binary_Indexed_Tree_Range_Sum_Query(int N) : N(N), node(vector<long long>(N + 1, 0)) {
}
void update(int idx, long long var) {
for (++idx; idx <= N; idx += idx & -idx) node[idx] += var;
}
long long getvar(int idx) {
long long ret = 0;
for (++idx; idx >= 1; idx -= idx & -idx) ret += node[idx];
return ret;
}
};
int main() {
int N,M; cin >> N;
M = 2 * N;
V<ll> a(M);
string S;
REP(i,M){
char c;
cin >> c >> a[i];
S.push_back(c);
}
V<V<ll>> costw(N+1,V<ll>(N+1,0)), costb(N + 1, V<ll>(N + 1, 0));
Binary_Indexed_Tree_Range_Sum_Query BITw(N+1),BITb(N+1);
REP(i,M){
if (S[i] == 'W') {
ll tmp = BITw.getvar(N) - BITw.getvar(a[i]);
for (int j = 0; j <= N; ++j) {
costw[a[i]][j] = tmp + BITb.getvar(N) - BITb.getvar(j);
}
BITw.update(a[i], 1);
}
if (S[i] == 'B') {
ll tmp = BITb.getvar(N) - BITb.getvar(a[i]);
for (int j = 0; j <= N; ++j) {
costb[a[i]][j] = tmp + BITw.getvar(N) - BITw.getvar(j);
}
BITb.update(a[i], 1);
}
}
V<V<ll>> dp(N + 1, V<ll>(N + 1, LINF));
dp[0][0] = 0;
dp[1][0] = costw[1][1];
dp[0][1] = costb[1][1];
for(int i = 0; i <= N; ++i){
for(int j = 0; j <= N; ++j){
if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j] + costw[i][j];
if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1] + costb[j][i];
if (i > 0 && j > 0) dp[i][j] = min(dp[i - 1][j] + costw[i][j], dp[i][j - 1] + costb[j][i]);
}
}
cout << dp[N][N] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Sorted and Sorted |
User |
ningenMe |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
3849 Byte |
Status |
AC |
Exec Time |
191 ms |
Memory |
94336 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 |
147 ms |
73856 KB |
1_015.txt |
AC |
18 ms |
11008 KB |
1_016.txt |
AC |
109 ms |
54912 KB |
1_017.txt |
AC |
42 ms |
22784 KB |
1_018.txt |
AC |
2 ms |
512 KB |
1_019.txt |
AC |
11 ms |
7680 KB |
1_020.txt |
AC |
121 ms |
64256 KB |
1_021.txt |
AC |
43 ms |
25344 KB |
1_022.txt |
AC |
24 ms |
13312 KB |
1_023.txt |
AC |
113 ms |
55552 KB |
1_024.txt |
AC |
187 ms |
90880 KB |
1_025.txt |
AC |
190 ms |
94336 KB |
1_026.txt |
AC |
190 ms |
94336 KB |
1_027.txt |
AC |
191 ms |
94336 KB |
1_028.txt |
AC |
191 ms |
94336 KB |
1_029.txt |
AC |
190 ms |
94336 KB |
1_030.txt |
AC |
191 ms |
94336 KB |
1_031.txt |
AC |
191 ms |
94336 KB |
1_032.txt |
AC |
188 ms |
94336 KB |
1_033.txt |
AC |
189 ms |
94336 KB |
1_034.txt |
AC |
190 ms |
94336 KB |
1_035.txt |
AC |
189 ms |
94336 KB |