제출 #1338123

#제출 시각아이디문제언어결과실행 시간메모리
1338123khanhphucscratchHiring (IOI09_hiring)C++20
100 / 100
265 ms23308 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool cmp(const pair<int, int> x, const pair<int, int> y)
{
    return x.first * y.second < x.second * y.first;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, w; cin>>n>>w;
    vector<pair<pair<int, int>, int>> a(n);
    for(int i = 0; i < n; i++){
        cin>>a[i].first.first>>a[i].first.second;
        a[i].second = i+1;
    }
    sort(a.begin(), a.end(), [&](auto &x, auto &y){return cmp(x.first, y.first);});
    int bestnum = 0, bestplace = 0;
    pair<int, int> bestmoney = {0, 0};
    //Calculate the answer
    priority_queue<pair<int, int>> st;
    int cursum = 0;
    for(int i = 0; i < n; i++){
        int nume = a[i].first.first, denom = a[i].first.second;
        st.push({denom, a[i].second}); cursum += denom;
        while(st.top().second != a[i].second && nume * cursum > denom*w){
            cursum -= st.top().first; st.pop();
        }
        if(nume * cursum <= denom*w){
            int curnum = st.size();
            pair<int, int> curmoney = make_pair(nume * cursum, denom);
            if(bestnum < curnum){
                bestnum = curnum; bestplace = i;
                bestmoney = curmoney;
            }
            if(bestnum == curnum && cmp(curmoney, bestmoney) == 1){
                bestplace = i;
                bestmoney = curmoney;
            }
        }
    }
    cout<<bestnum<<'\n';
    if(bestnum == 0) return 0;
    //Trace
    while(st.size() > 0) st.pop();
    for(int i = 0; i < bestplace; i++) st.push({a[i].first.second, a[i].second});
    vector<int> ans = {a[bestplace].second};
    while(st.size() > bestnum - 1) st.pop();
    while(st.size() > 0){
        ans.push_back(st.top().second); st.pop();
    }
    sort(ans.begin(), ans.end());
    for(int i : ans) cout<<i<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...