제출 #952049

#제출 시각아이디문제언어결과실행 시간메모리
952049Angus_YeungHiring (IOI09_hiring)C++17
100 / 100
305 ms17868 KiB
#include <bits/stdc++.h> #define val first #define id second #define pii pair<ll, ll> typedef long long ll; const ll MOD = 1000000007LL; const ll INF = 1e15; using namespace std; struct worker { ll s, q, id; }; ll n, w, sum; pair<ll, long double> ans; worker a[500010]; priority_queue<pii> q; long double f(worker x) { return x.s*1.0/x.q; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n >> w; for (int i = 1; i <= n; i++) { cin >> a[i].s >> a[i].q; a[i].id = i; } sort(a+1, a+n+1, [&](worker x, worker y) -> bool { return f(x) < f(y); }); sum = 0; ans = {0, 0}; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) { q.push({a[i].q, a[i].id}); sum += a[i].q; while (!q.empty() && f(a[i])*sum > w) { sum -= q.top().val; q.pop(); } if ((ll)q.size() > ans.first) { ans = {(ll)q.size(), sum*f(a[i])}; } else if ((ll)q.size() == ans.first && sum*f(a[i]) < ans.second) { ans = {(ll)q.size(), sum*f(a[i])}; } } if (ans.first == 0) { cout << "0\n"; return 0; } sum = 0; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) { q.push({a[i].q, a[i].id}); sum += a[i].q; while (!q.empty() && f(a[i])*sum > w) { sum -= q.top().val; q.pop(); } if (ans.first == (ll)q.size() && ans.second >= sum*f(a[i])) { cout << ans.first << "\n"; while (!q.empty()) { cout << q.top().id << "\n"; q.pop(); } return 0; } } return 0; }
#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...