Submission #817996

#	Time	Username	Problem	Language	Result	Execution time	Memory
817996		Liudas	Hiring (IOI09_hiring)	C++17	100 / 100	633 ms	21308 KiB

hiring

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
struct node{
    double Q;
    double P;
    double U;
    int id;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long N, W;
    double H = 0, BP = 0;
    cin >> N >> W;
    vector<node> arr(N);
    for(int i = 0; i < N; i ++){
        cin >> arr[i].P >> arr[i].Q;
        arr[i].U = arr[i].P/arr[i].Q;
        arr[i].id = i + 1;
    }
    sort(arr.begin(), arr.end(), [&](node a, node b){return a.U < b.U;});
    priority_queue<pair<double, int>> que;
    bitset<500500> in, best;
    double qual = 0;
    for(int i = 0; i < N; i ++){
        qual += arr[i].Q;
        que.push({arr[i].Q, arr[i].id});
        in[arr[i].id] = 1;
        while(qual * arr[i].U > W){
            qual -= que.top().first;
            in[que.top().second] = 0;
            que.pop();
        }
        if(que.size() > H){
            H = que.size();
            best = in;
            BP = qual * arr[i].U;
        }
        else if(que.size() == H && BP > qual * arr[i].U){
            BP = qual * arr[i].U;
            best = in;
        }
    }
    cout << H << endl;
    for(int i = 0; i < N+1; i ++){
        if(best[i])
        cout << i << endl;
    }
    return 0;
}

• 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