Submission #818017

#	Time	Username	Problem	Language	Result	Execution time	Memory
818017		Liudas	Hiring (IOI09_hiring)	C++17	100 / 100	244 ms	19096 KiB

hiring

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
struct node{
    long long Q;
    long long 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 = (double)arr[i].P/(double)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<int, int>> que;
    long long qual = 0, id = 0;
    for(int i = 0; i < N; i ++){
        qual += arr[i].Q;
        que.push({arr[i].Q, arr[i].id});
        while((double)qual * arr[i].U > W){
            qual -= que.top().first;
            que.pop();
        }
        if(que.size() > H){
            H = que.size();
            BP = qual * arr[i].U;
            id = i + 1;
        }
        else if(que.size() == H && BP > qual * arr[i].U){
            BP = qual * arr[i].U;
            id = i + 1;
        }
    }
    while(!que.empty())que.pop();
    qual = 0;
    bitset<500500> in;
    for(int i = 0; i < id; 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();
        }
    }
    cout << H << endl;
    for(int i = 0; i <= N; i ++){
        if(in[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