Submission #703261

#	Time	Username	Problem	Language	Result	Execution time	Memory
703261		finn__	Hiring (IOI09_hiring)	C++17	6 / 100	310 ms	13056 KiB

hiring

#include <bits/stdc++.h>
using namespace std;

#define N 500000

struct Worker
{
    int64_t s, q;
    size_t i;
};

Worker y[N];

bool compare_worker(Worker const &a, Worker const &b)
{
    return a.s * b.q > a.q * b.s;
}

int main()
{
    size_t n;
    long double w;
    cin >> n >> w;

    for (size_t i = 0; i < n; ++i)
    {
        cin >> y[i].s >> y[i].q;
        y[i].i = i;
    }
    sort(y, y + n, compare_worker);

    long double c = y[0].s, min_c = DBL_MAX;
    Worker *p1 = y, *p2 = y + 1, *best1 = 0, *best2 = 0;

    while (p2 < y + n)
    {
        if (c + (long double)p2->q / (long double)p1->q * (long double)p1->s > w)
        {
            if (p2 - p1 > best2 - best1 || (p2 - p1 == best2 - best1 && c < min_c))
                best1 = p1, best2 = p2, min_c = c;
            c -= (long double)p1->s;
            c *= (long double)p1->q / (long double)(p1 + 1)->q;
            ++p1;
        }
        else
        {
            c += (long double)p2->q / (long double)p1->q * (long double)p1->s;
            ++p2;
        }
    }

    if (p2 - p1 > best2 - best1 || (p2 - p1 == best2 - best1 && c < min_c))
        best1 = p1, best2 = p2, min_c = c;

    cout << best2 - best1 << '\n';
    while (best1 < best2)
        cout << best1->i + 1 << '\n', best1++;
}

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