Submission #456341

#	Time	Username	Problem	Language	Result	Execution time	Memory
456341		chunghan	Hiring (IOI09_hiring)	C++17	1 / 100	513 ms	18264 KiB

hiring

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

ll N, W, sum, rst, psum = 5e13, pS = 1;
pair<pair<ll, ll>, int> D[500005];
pair<pair<ll, ll>, int> max_k;
priority_queue<pair<pair<ll, ll>, int>, vector<pair<pair<ll, ll>, int>>, less<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;
}

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


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 (sum*S > W*Q && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (rst < (ll)pq.size()) {
            rst = pq.size();
            psum = sum;
            max_k = D[i];
        } else if (rst == (ll)pq.size()) {
            if (sum*S*max_k.first.first < (double)psum*max_k.first.second*Q) {
                psum = sum;
                max_k = D[i];
            }
        }
    }
    cout << rst << '\n';
    sum = 0;
    int cnt = 0;
    ll Qr = max_k.first.first, Sr = max_k.first.second, im = max_k.second;
    if (Qr == 0 && Sr == 0)
        return 0;
    while(!pq.empty()) pq.pop();
    sort(D, D+N, cmp2);
    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 (sum*S > W*Q && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (i == im) {
            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:57:9: warning: unused variable 'cnt' [-Wunused-variable]
   57 |     int cnt = 0;
      |         ^~~

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