CF Round #653 E1 - Reading Books (easy version)


Tags:cpcodeforcesdiv3greedy

問題

https://codeforces.com/contest/1374/problem/E1

問題文

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

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

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

制約

  • 1kn2×1051 \le k \le n \le 2 \times 10^5
  • 1ti1041 \le t_i \le 10^4
  • ai,bi{0,1}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 人とも好きな本を 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;
}