Submission #1036037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036037		sleepntsheep	Hiring (IOI09_hiring)	C++17	100 / 100	440 ms	25424 KiB

hiring

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ll long long 
using ld = long double;

ll n, w;
struct worker
{
    int s, q, i;
} a[1<<19];

set<pair<ll, int>> st;
pair<int, ld> opt = {0, -1e18};
ll opt_i, cur;

void add(ll i)
{
    cur += a[i].q;
    st.emplace(a[i].q, i);
}

void del()
{
    auto it = prev(st.end());
    cur -= it->first;
    st.erase(it);
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> w;
    for (int i = 1; i <= n; ++i) cin >> a[i].s >> a[i].q, a[i].i = i;

    sort(a+1, a+1+n, [](const worker &a, const worker &b){
            return ld(a.s)/ld(a.q) < ld(b.s)/ld(b.q);
    });

    for (int i = 1; i <= n; ++i)
    {
        ld u = ld(a[i].s)/ld(a[i].q);
        add(i);
        while (cur * u > w) del();
        pair<int, ld> c2 = {st.size(), -cur * u};
        if (c2 > opt) opt = c2, opt_i = i;
        //cout << " " << i << " " << st.size() << " " << u << " " << cur << '\n';
    }

    st.clear();
    cur = 0;

    for (int i = 1; i <= opt_i; ++i)
    {
        ld u = ld(a[i].s)/ld(a[i].q);
        add(i);
        while (cur * u > w) del();
    }

    cout << st.size() << '\n';
    for (auto [u, v] : st) cout << a[v].i << '\n';

    return 0;
}

• 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