Submission #456354

#	Time	Username	Problem	Language	Result	Execution time	Memory
456354		chunghan	Hiring (IOI09_hiring)	C++17	100 / 100	471 ms	23600 KiB

hiring

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

ll N, W, sum, rst, im;
double psum = 1e18;
pair<pair<ll, ll>, int> D[500005];
pair<pair<ll, ll>, int> max_k;
priority_queue<pair<pair<ll, ll>, int>> pq;

bool cmp(pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b) {
    pair<ll, ll> x = a.first, y = b.first;
    return x.first * y.second > y.first * x.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        int q, s;
        cin >> s >> q;
        D[i] = {{q, s}, i};
    }
    sort(D, D+N, cmp);
    for (int i = 0; i < N; i++) {
        pair<ll, ll> E = D[i].first;
        ll Q = E.first, S = E.second;
        pq.push(D[i]);
        sum += Q;
        while ((double)sum/Q*S > W && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (rst < (ll)pq.size()) {
            rst = pq.size();
            psum = (double)sum*S/Q;
            max_k = D[i];
            im = i;
        } else if (rst == (ll)pq.size()) {
            if ((double)sum/Q*S < psum) {
                psum = (double)sum*S/Q;
                max_k = D[i];
                im = i;
            }
        }
    }
    sum = 0;
    ll Qr = max_k.first.first, Sr = max_k.first.second;
    if (rst == 0) {
        cout << 0 <<endl;
        return 0;
    }
    while(!pq.empty()) pq.pop();
    for (int i = 0; i < N; i++) {
        pair<ll, ll> E = D[i].first;
        ll Q = E.first, S = E.second;
        pq.push(D[i]);
        sum += Q;
        while ((double)sum/Q*S > W && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (i == im) {
            cout << pq.size() << '\n';
            while (!pq.empty()) {
                cout << pq.top().second + 1 << '\n';
                pq.pop();
            }
            break;
        }
    }
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:51:8: warning: unused variable 'Qr' [-Wunused-variable]
   51 |     ll Qr = max_k.first.first, Sr = max_k.first.second;
      |        ^~
hiring.cpp:51:32: warning: unused variable 'Sr' [-Wunused-variable]
   51 |     ll Qr = max_k.first.first, Sr = max_k.first.second;
      |                                ^~

• Subtask 1: 30 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6