問題
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; }