IOI '09 P2 - Hiring

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    int n;
    long long w;
    cin >> n >> w;
    vector<int> s(n), q(n);
    for (int i = 0; i < n; ++i) cin >> s[i] >> q[i];

    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i;
    sort(v.begin(), v.end(), [&s, &q](int i, int j) {
        return s[i]*q[j] < s[j]*q[i];
    });

    int maxWorkers = 0, lastWorker = 0;
    long long minPayN = w+1, minPayD = 1; // numerator, denominator

    priority_queue<pair<int, int>> pq;
    long long qSum = 0; int curWorkers = 0;
    for (int p = 0; p < n; ++p) {
        int i = v[p];
        long long targetN = w*q[i], targetD = s[i]; // numerator, denominator
        pq.emplace(q[i], i);
        qSum += q[i];
        ++curWorkers;
        while (qSum*targetD > targetN) {
            qSum -= pq.top().first;
            pq.pop();
            --curWorkers;
        }
        long long payN = s[i]*qSum, payD = q[i]; // numerator, denominator
        if (curWorkers > maxWorkers || curWorkers == maxWorkers && payN*minPayD < minPayN*payD) {
            maxWorkers = curWorkers;
            lastWorker = p;
            minPayN = payN, minPayD = payD;
        }
    }

    cout << maxWorkers << endl;
    sort(v.begin(), v.begin()+lastWorker+1, [&q](int i, int j) {
        return q[i] < q[j];
    });
    for (int i = 0; i < maxWorkers; ++i) cout << v[i]+1 << endl;
    cout << endl;
    return 0;
}