BEN2のブログ

たまに書いています。

ABC 160 E - Red and Green Apples

競技プログラミング

ABC 160 E - Red and Green Apples についてのメモを残します。

リンゴは好きです

赤色のリンゴが A 個、緑色のリンゴが B 個、無色のリンゴが C 個ある。
無色のリンゴは、赤色または緑色に着色できる。
赤色のリンゴを X \, ( X \leq A) 個、緑色のリンゴを Y \, ( Y \leq B) 個食べるとき、"美味しさ" の総和の最大値はいくらか。

赤色と緑色のリンゴについて、あらかじめ "美味しさ" の大きい順にそれぞれ X 個、 Y 個取り出しておく。
そして、色を無視して "美味しさ" の大きい順に X + Y 個食べるとよい。

f:id:BEN2suzuka:20200329014143p:plain

選ばれなかった赤・緑のリンゴの個数と選ばれた無色のリンゴの個数は一致する。
無色のリンゴを適宜着色することにより、食べる X + Y 個の内訳を赤 X 個、緑 Y 個にすることが可能。

f:id:BEN2suzuka:20200329015109p:plain

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

int main() {
  int X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;
  vector<int> p(A), q(B), r(C);
  for (int i = 0; i < A; i++) cin >> p.at(i);
  for (int i = 0; i < B; i++) cin >> q.at(i);
  for (int i = 0; i < C; i++) cin >> r.at(i);
  sort(p.begin(), p.end(), greater<int>());
  sort(q.begin(), q.end(), greater<int>());
  priority_queue<int> pq;
  for (int i = 0; i < X; i++) pq.push(p.at(i));
  for (int i = 0; i < Y; i++) pq.push(q.at(i));
  for (int i = 0; i < C; i++) pq.push(r.at(i));
  long long ans = 0;
  for (int i = 0; i < X + Y; i++) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << endl;
}