Submission #1325704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325704		kasamchi	Hiring (IOI09_hiring)	C++20	2 / 100	1595 ms	6304 KiB

hiring

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    long long W;
    cin >> N >> W;

    vector<int> S(N), Q(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> Q[i];
    }

    vector<int> C(N);
    for (int i = 0; i < N; i++) {
        C[i] = i;
    }
    sort(C.begin(), C.end(), [&] (int a, int b) {return S[a] * Q[b] < Q[a] * S[b];});

    int ans = 0, apos = 0;
    pair<long long, long long> acst;
    for (int i = 0; i < N; i++) {
        vector<int> v;
        for (int j = 0; j <= i; j++) {
            v.push_back(Q[C[j]]);
        }
        sort(v.begin(), v.end());

        long long sum = 0;
        int cur = i + 1;
        for (int j = 0; j <= i; j++) {
            sum += v[C[j]];
            if (sum * S[C[i]] > W * Q[C[i]]) {
                sum -= v[C[j]];
                cur = j;
                break;
            }
        }

        pair<long long, long long> cst = make_pair(sum * S[C[i]], Q[C[i]]);
        if (cur > ans || (cur == ans && cst.first * acst.second < cst.second * acst.first)) {
            ans = cur;
            apos = i;
            acst = cst;
        }
    }
    cout << ans << '\n';
    for (int i = 0; i < ans; i++) {
        cout << i << '\n';
    }
}

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