Submission #817989

#	Time	Username	Problem	Language	Result	Execution time	Memory
817989		Liudas	Hiring (IOI09_hiring)	C++17	50 / 100	303 ms	24012 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;
    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<double> que;
    double qual = 0;
    for(int i = 0; i < N; i ++){
        qual += arr[i].Q;
        que.push(arr[i].Q);
        while(qual * arr[i].U > W){
            qual -= que.top();
            que.pop();
        }
        H = max(H, (double)que.size());
    }
    cout << H << endl;
    vector<int> ans(H, 1);
    for(int i : ans){
        cout << i << endl;
    }
    return 0;
}

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