Submission #1036036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036036		12345678	Hiring (IOI09_hiring)	C++17	27 / 100	1597 ms	17852 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 "<<i<<' '<<v[i].second<<' '<<cnt<<'\n';
        mx=max(mx, {cnt, {-w, i}});
    }
    cout<<(int)mx.first<<'\n';
    for (int i=0; i<mx.first; i++) cout<<0<<'\n';
}

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