# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
501984 |
2022-01-05T05:24:41 Z |
blue |
Hiring (IOI09_hiring) |
C++17 |
|
426 ms |
28080 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
#define sz(x) int(x.size())
struct worker
{
ll S;
ll Q;
int i;
};
struct frac
{
ll n;
ll d;
};
bool operator < (frac A, frac B)
{
if(B.d * A.d < 0) return A.n * B.d > B.n * A.d;
else return A.n * B.d < B.n * A.d;
}
worker P[1+500'000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
ll W;
cin >> W;
for(int i = 1; i <= N; i++)
{
cin >> P[i].S >> P[i].Q;
P[i].i = i;
}
sort(P+1, P+N+1, [] (worker u, worker v)
{
return u.S * v.Q < v.S * u.Q;
});
multiset<ll> qual;
ll qual_sum = 0;
pair<ll, frac> ans{0, {0,1}}; //workers, -money, take max
int ans_ind = -1;
for(int i = 1; i <= N; i++)
{
qual.insert(P[i].Q);
qual_sum += P[i].Q;
// while(qual_sum * (P[i].S / P[i].Q) > W)
while(qual_sum * P[i].S > W * P[i].Q)
{
qual_sum -= *qual.rbegin();
qual.erase(qual.find(*qual.rbegin()));
}
pair<ll, frac> curr = {sz(qual), frac{-qual_sum * P[i].S, P[i].Q}};
if(curr > ans)
{
ans = curr;
ans_ind = i;
}
}
sort(P+1, P+ans_ind+1, [] (worker u, worker v)
{
return u.Q < v.Q;
});
cout << ans.first << '\n';
for(int i = 1; i <= ans.first; i++) cout << P[i].i << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
2 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
464 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
3 ms |
456 KB |
Output is correct |
12 |
Correct |
4 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
628 KB |
Output is correct |
14 |
Correct |
6 ms |
940 KB |
Output is correct |
15 |
Correct |
9 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
9 ms |
1388 KB |
Output is correct |
5 |
Correct |
23 ms |
3012 KB |
Output is correct |
6 |
Correct |
186 ms |
15880 KB |
Output is correct |
7 |
Correct |
209 ms |
21756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
6280 KB |
Output is correct |
2 |
Correct |
62 ms |
6220 KB |
Output is correct |
3 |
Correct |
74 ms |
6252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
10668 KB |
Output is correct |
2 |
Correct |
88 ms |
10720 KB |
Output is correct |
3 |
Correct |
99 ms |
10668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
24260 KB |
Output is correct |
2 |
Correct |
281 ms |
24228 KB |
Output is correct |
3 |
Correct |
261 ms |
24276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
358 ms |
28080 KB |
Output is correct |
2 |
Correct |
426 ms |
27996 KB |
Output is correct |
3 |
Correct |
368 ms |
28076 KB |
Output is correct |