問題
https://codeforces.com/contest/1374/problem/E1 (新しいタブで開く)
問題文
個の本がある。このうちから、以下の条件を満たすように本を選ぶ。
Alice は少なくとも 本好き ()。Bob () についても同様。
読む時間 () を最小化する。
選んだ本を全部読むには、少なくともどれくらいかかる?
制約
サンプル
I/O 1
8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0
18
I/O 2
5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0
8
I/O 3
5 3
3 0 0
2 1 0
3 1 0
5 0 1
3 0 1
-1
考察
本をグループ分けする。
- Alice が好きな本
- Bob が好きな本
- 2 人とも好きな本
2 人とも好きな本を 本選ぶとすると、2 人ともそれぞれ残り 本を読むことになる。
その選び方は、グループ内から少ない順にとっていくのが最適。
本のうちから を全通り探索しても間に合う。
コード
https://codeforces.com/contest/1374/submission/126812598 (新しいタブで開く)
int main() {
int n, k;
cin >> n >> k;
ll alice = 0, bob = 0;
vector<vector<ll>> book(3);
vector<vector<ll>> sum(3);
rep(i, n) {
ll time, a, b;
cin >> time >> a >> b;
if (a) alice++;
if (b) bob++;
if (a || b) {
book[2 * a + b - 1].push_back(time);
}
}
if (alice < k || bob < k) {
cout << -1 << endl;
return 0;
}
ll ans = 1e10;
rep(i, 3) {
sort(book[i].begin(), book[i].end());
sum[i].push_back(0);
rep(j, book[i].size()) {
sum[i].push_back(sum[i][j] + book[i][j]);
}
}
rep(c, min((int) book[2].size(), k) + 1) {
if (k - c <= book[0].size() && k - c <= book[1].size()) {
ans = min(ans, sum[2][c] + sum[1][k - c] + sum[0][k - c]);
}
}
cout << ans << endl;
return 0;
}