Educational Codeforces 62 C - Playlist (R1600)

楽しかった

問題へのリンク

問題概要

個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは

• (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値)

で決まる。このスコアの最大値を求めよ。

制約

• 

考えたこと

「ある量を fix すると Greedy に決まる」という構造の問題！！

今回は「選んだアイテムの美しさの最小値」を fix すると、

• 美しさがそれ以上のアイテムの中から「時間」が大きい順に 個とる

というのが最適であることがわかる。よって美しさの最小値を 通り試す。ここで、美しさの値を下げるとき、増えるアイテムは 1 個であることから、priority_queue などを用いて「上位 個」を高速に更新できる。

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<long long> t(N), b(N);
    for (int i = 0; i < N; ++i) cin >> t[i] >> b[i];
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return b[i] > b[j]; });

    long long res = 0;
    priority_queue<long long, vector<long long>, greater<long long> > que;
    long long sum = 0;
    for (auto i : ids) {
        if (que.size() < K) {
            que.push(t[i]);
            sum += t[i];
        }
        else {
            long long v = que.top();
            if (v < t[i]) {
                que.pop();
                que.push(t[i]);
                sum -= v;
                sum += t[i];
            }
        }
        res = max(res, sum * b[i]);
    }
    cout << res << endl;
}