E1 - Reading Books (easy version)

問題

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

問題文

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

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

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

制約

• $1 \le k \le n \le 2 \times 10^5$
• $1 \le t_i \le 10^4$
• $a_i, b_i \in \{0, 1\}$

サンプル

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

$k$ 本のうちから $c$ を全通り探索しても間に合う。

コード

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