제출 #1325499

#제출 시각아이디문제언어결과실행 시간메모리
1325499kasamchiHiring (IOI09_hiring)C++20
7 / 100
1595 ms9976 KiB
#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<pair<pair<int, int>, int>> C(N);
    for (int i = 0; i < N; i++) {
        C[i] = make_pair(make_pair(S[i], Q[i]), i + 1);
    }
    sort(C.begin(), C.end(), [] (pair<pair<int, int>, int> pa, pair<pair<int, int>, int> pb) {
        pair<int, int> a = pa.first, b = pb.first;
        if ((long long)a.first * b.second != (long long)a.second * b.first) {
            return (long long)a.first * b.second > (long long)a.second * b.first;
        } else {
            return a.first < b.first;
        }
    });

    int ans = 0, apos = -1;
    double aw = -1;
    for (int i = 0; i < N; i++) {
        double w = 0;
        int j = i;
        while (j < N) {
            w += (double)C[i].first.first / C[i].first.second * C[j].first.second;
            if (w > W) {
                w -= (double)C[i].first.first / C[i].first.second * C[j].first.second;
                break;
            }
            j++;
        }
        if (j - i > ans || (j - i == ans && w < aw)) {
            ans = j - i;
            apos = i;
            aw = w;
        }
    }

    cout << ans << '\n';
    for (int i = 0; i < ans; i++) {
        cout << C[apos + i].second << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...