Submission #1036042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036042		12345678	Hiring (IOI09_hiring)	C++17	54 / 100	1580 ms	20536 KiB

hiring

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

#define ll long long

ll n, s[nx], q[nx], w, res[nx];
vector<pair<double, ll>> v;
pair<ll, pair<double, ll>> mx;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>w;
    for (int i=1; i<=n; i++) cin>>s[i]>>q[i], v.push_back({((double)s[i])/q[i], i});
    sort(v.begin(), v.end());
    for (int i=0; i<n; i++)
    {
        ll cnt=1;
        double cost=s[v[i].second];
        vector<ll> tmp;
        for (int j=0; j<i; j++) tmp.push_back(q[v[j].second]);
        sort(tmp.begin(), tmp.end());
        reverse(tmp.begin(), tmp.end());
        while (!tmp.empty()&&cost+((double)tmp.back())*(s[v[i].second])/q[v[i].second]<=w) cnt++, cost+=((double)tmp.back())*(s[v[i].second])/q[v[i].second], tmp.pop_back();
        //cout<<"debug "<<cnt<<' '<<v[i].second<<' '<<w<<'\n';
        mx=max(mx, {cnt, {-cost, i}});
    }
    cout<<(int)mx.first<<'\n';
    double cost=s[v[mx.second.second].second];
    cout<<v[mx.second.second].second<<'\n';
    vector<pair<ll, ll>> tmp;
    for (int i=0; i<mx.second.second; i++) tmp.push_back({q[v[i].second], v[i].second});
    sort(tmp.begin(), tmp.end());
    reverse(tmp.begin(), tmp.end());
    while (!tmp.empty()&&cost+((double)tmp.back().first)*(s[v[mx.second.second].second])/q[v[mx.second.second].second]<=w) cout<<(int)tmp.back().second<<'\n', cost+=((double)tmp.back().first)*(s[v[mx.second.second].second])/q[v[mx.second.second].second], tmp.pop_back();
}

• Subtask 1: 24 / 30
• Subtask 2: 12 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6