Submission #998659

#	Time	Username	Problem	Language	Result	Execution time	Memory
998659		bachhoangxuan	Hiring (IOI09_hiring)	C++17	66 / 100	305 ms	24900 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5+5;
int N,S[maxn],Q[maxn],W;
int sum;
priority_queue<int> pq;

signed main(){
    cin >> N >> W;
    for(int i=1;i<=N;i++) cin >> S[i] >> Q[i];
    vector<int> ord(N);
    iota(ord.begin(),ord.end(),1);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return S[x]*Q[y]<S[y]*Q[x];
    });
    pair<int,int> Max={-1,-1};
    for(int x:ord){
        int mx=(W*Q[x])/S[x];
        pq.push(Q[x]);sum+=Q[x];
        while(sum>mx) sum-=pq.top(),pq.pop();
        Max=max(Max,{(int)pq.size(),x});
    }
    cout << Max.first << '\n';
    int a=Max.second;
    vector<int> cur;
    for(int x:ord){
        cur.push_back(x);
        if(x==a) break;
    }
    W=(W*Q[a])/S[a];
    sort(cur.begin(),cur.end(),[&](int x,int y){
        return Q[x]<Q[y];
    });
    for(int x:cur){
        W-=Q[x];
        if(W<0) break;
        cout << x << '\n';
    }
}

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