제출 #996909

#제출 시각아이디문제언어결과실행 시간메모리
996909GhettoHiring (IOI09_hiring)C++17
60 / 100
1598 ms32976 KiB
#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'; }
#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...