Submission #456337

#	Time	Username	Problem	Language	Result	Execution time	Memory
456337		chunghan	Hiring (IOI09_hiring)	C++17	5 / 100	418 ms	21564 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<ll, ll> max_k;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, less<pair<ll, ll>>> 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(E);
        sum += Q;
        while (sum*S > W*Q && !pq.empty()) {
            sum -= pq.top().first;
            pq.pop();
        }
        if (rst < (ll)pq.size()) {
            rst = pq.size();
            psum = sum;
            max_k = E;
        } else if (rst == (ll)pq.size()) {
            if (sum*S*max_k.first < (double)psum*max_k.second*Q) {
                psum = sum;
                max_k = E;
            }
        }
    }
    cout << rst << '\n';
    sum = 0;
    int cnt = 0;
    ll Qr = max_k.first, Sr = max_k.second;
    if (Qr == 0 && Sr == 0)
        return 0;
    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, index = D[i].second;
        if (cnt == rst)
            break;
        if ((sum + Q) * Sr <= W * Qr && Q*Sr >= Qr*S) {
            sum += Q;
            cout << index+1 << '\n';
            cnt ++;
        }
    }
    return 0;
}

• Subtask 1: 5 / 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