/*
Zadanie: Hiring
Autor: Tomasz Kwiatkowski
*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;
struct frac
{
long long p, q;
frac () {}
frac (long long a, long long b = 1) : p(a), q(b) {}
bool operator==(frac x)
{
return p*x.q == q*x.p;
}
bool operator<=(frac x)
{
return p*x.q <= q*x.p;
}
bool operator<(frac x)
{
return p*x.q < q*x.p;
}
frac operator*(long long x)
{
return frac(p*x, q);
}
};
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
long long w;
cin >> n >> w;
vector<pair<frac, int>> sorted(n);
int i = 0;
for (auto& [x, ind] : sorted) {
cin >> x.p >> x.q;
ind = i++;
}
vector<pair<frac, int>> candidates(sorted);
sort(sorted.begin(), sorted.end(), [](auto lhs, auto rhs) {
if (lhs.fi == rhs.fi) {
if (lhs.fi.q == rhs.fi.q)
return lhs.se < lhs.se;
return lhs.fi.q < rhs.fi.q;
}
return rhs.fi < lhs.fi;
});
sort(candidates.begin(), candidates.end(), [](auto lhs, auto rhs) {
if (lhs.fi.q == rhs.fi.q)
return lhs.se < lhs.se;
return lhs.fi.q < rhs.fi.q;
});
vector<bool> ok(n, true);
int j = 0;
int cnt = 0;
frac money(w);
int k = 0;
long long sum_q = 0;
for (auto [x, ind] : sorted) {
if (ok[ind])
++cnt, sum_q += x.q;
ok[ind] = false;
while (j < n && (x*(sum_q + candidates[j].fi.q*ok[candidates[j].se]) <= frac(w))) {
sum_q += candidates[j].fi.q*ok[candidates[j].se];
cnt += ok[candidates[j].se];
ok[candidates[j].se] = false;
++j;
}
if (x*sum_q <= frac(w)) {
if (cnt > k)
k = cnt, money = x*sum_q;
else if (cnt == k && (x*sum_q < money))
money = x*sum_q;
}
sum_q -= x.q;
--cnt;
}
cout << k << '\n';
ok = vector<bool>(n, true);
vector<bool> chosen(n, false);
j = 0;
cnt = 0;
sum_q = 0;
for (auto [x, ind] : sorted) {
if (ok[ind])
++cnt, sum_q += x.q;
ok[ind] = false;
chosen[ind] = true;
while (j < n && (x*(sum_q + candidates[j].fi.q*ok[candidates[j].se]) <= frac(w))) {
if (ok[candidates[j].se])
chosen[candidates[j].se] = true;
sum_q += candidates[j].fi.q*ok[candidates[j].se];
cnt += ok[candidates[j].se];
ok[candidates[j].se] = false;
++j;
}
if (x*sum_q <= frac(w) && cnt == k && (x*sum_q == money)) {
for (int i = 0; i < n; ++i)
if (chosen[i])
cout << i + 1 << '\n';
return 0;
}
sum_q -= x.q;
chosen[ind] = false;
--cnt;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
412 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
588 KB |
Output is correct |
12 |
Correct |
3 ms |
716 KB |
Output is correct |
13 |
Correct |
3 ms |
716 KB |
Output is correct |
14 |
Correct |
5 ms |
844 KB |
Output is correct |
15 |
Correct |
5 ms |
972 KB |
Output is correct |
# |
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 |
8 ms |
1228 KB |
Output is correct |
5 |
Correct |
19 ms |
3424 KB |
Output is correct |
6 |
Correct |
136 ms |
15032 KB |
Output is correct |
7 |
Correct |
142 ms |
20196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 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 |
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 |
46 ms |
5896 KB |
Output is correct |
2 |
Correct |
49 ms |
5836 KB |
Output is correct |
3 |
Correct |
44 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
10124 KB |
Output is correct |
2 |
Correct |
71 ms |
10088 KB |
Output is correct |
3 |
Correct |
71 ms |
10136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
185 ms |
22596 KB |
Output is correct |
2 |
Correct |
171 ms |
22660 KB |
Output is correct |
3 |
Correct |
171 ms |
22592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
25284 KB |
Output is correct |
2 |
Correct |
190 ms |
25284 KB |
Output is correct |
3 |
Correct |
222 ms |
25232 KB |
Output is correct |