#include #include #include using namespace std; using ll = long long; void solve (int N, int X, int Y, vector>& custemer) { // 面白い。最初の考察として、先頭X+Y人が大事になることがわかる。 // なぜならi組目が部屋Aに割り当てられたとき、必ずX+Y+i組目も部屋Aに割り当てられるから。 // // ここから、次の問題に帰着する。 // 長さX+Yの数列A, Bが与えられる。 // 長さXの部分列を{1, 2, ..., X+Y}からとり、pとする。 // C[i] = A[i] (if i in p) // B[i] (if i not in p) // としたとき、Cの総和の最大値は? // これは次の考え方で解ける。 // 最初全項Aにいたとして、Y項だけBに転落させる。 // 総和の減少を最小にせよ。 // これはA[i]-B[i]を持っておけば貪欲にとれて、ソート分のO((X+Y)log(X+Y))で解ける。 vector A(X+Y), B(X+Y); for (int i = 0; i < X+Y; i++) { int cur = i; while (cur < N) { char c = custemer[cur].second; int P = custemer[cur].first; if (c == 'A') A[i] += P; if (c == 'B') B[i] += P; cur += X+Y; } } vector diff(X+Y); for (int i = 0; i < X+Y; i++) diff[i] = A[i]-B[i]; sort(diff.begin(), diff.end()); ll ans = 0; for (auto& a : A) ans += a; for (int i = 0; i < Y; i++) { ans -= diff[i]; } cout << ans << "\n"; } int main () { int N, X, Y; cin >> N >> X >> Y; vector> custemer(N); for (int i = 0; i < N; i++) { int P; char c; cin >> P >> c; custemer[i] = make_pair(P, c); } solve(N, X, Y, custemer); }