E1 - Reading Books (easy version)

cpcodeforcesdiv3greedy

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1374/problem/E1 (新しいタブで開く)

問題文

nn 個の本がある。このうちから、以下の条件を満たすように本を選ぶ。

Alice は少なくとも kk 本好き (ai=1a_i = 1)。Bob (bib_i) についても同様。
読む時間 (tit_i) を最小化する。

選んだ本を全部読むには、少なくともどれくらいかかる?

制約

サンプル

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

考察

本をグループ分けする。

2 人とも好きな本を cc 本選ぶとすると、2 人ともそれぞれ残り kck-c 本を読むことになる。
その選び方は、グループ内から少ない順にとっていくのが最適。

kk 本のうちから cc を全通り探索しても間に合う。

コード

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