제출 #998661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998661		bachhoangxuan	Hiring (IOI09_hiring)	C++17	100 / 100	314 ms	19272 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<pair<int,long double>,int> Max={{-1,-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(),-(long double)sum*S[x]/Q[x]},x});
    }
    cout << Max.first.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: 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