Submission #996909

#	Time	Username	Problem	Language	Result	Execution time	Memory
996909		Ghetto	Hiring (IOI09_hiring)	C++17	60 / 100	1598 ms	32976 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
using ldouble = long double;
using pli = pair<ldouble, int>;
const int MAX_N = 5e5 + 5;

int n;
ldouble m;
ldouble p[MAX_N], s[MAX_N];
pli a[MAX_N];

struct Answer {
    int count;
    ldouble sum;
};
bool is_worse(Answer x, Answer y) {
    if (x.count == y.count) return x.sum > y.sum;
    return x.count < y.count;
}

int main() {
   // freopen("hiring.in", "r", stdin), freopen("hiring.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> s[i];
        a[i] = {p[i] / s[i], i};
    }
    sort(a + 1, a + n + 1);

    Answer ans = {0, 0};
    vector<int> list;
    set<pli> ord;
    for (int j = 1; j <= n; j++) {
        int i = a[j].second;
        ord.insert({s[i], i});
        
        Answer new_ans = {0, 0};
        vector<int> new_list;
        ldouble tar = m / a[j].first;
        for (auto it = ord.begin(); it != ord.end(); it++) {
            if (new_ans.sum + it->first > tar) break;
            new_ans.count++, new_ans.sum += it->first;
            new_list.push_back(it->second);
        }
        new_ans.sum *= a[j].first;

        if (is_worse(new_ans, ans)) continue;
        ans = new_ans, list = new_list;
    }

    cout << list.size() << '\n';
    for (int x : list) cout << x << '\n';
}

• Subtask 1: 30 / 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