# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
490720 | 2021-11-29T01:28:54 Z | ntabc05101 | Hiring (IOI09_hiring) | C++14 | 295 ms | 15288 KB |
#include<bits/stdc++.h> using namespace std; #define taskname "" int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } else { if (fopen(taskname".in", "r")) { freopen(taskname".in", "r", stdin); freopen(taskname".out", "w", stdout); } } cin.tie(0)->sync_with_stdio(0); int n; long long w; cin >> n >> w; struct Sal { int s, q; double r; int idx; bool operator < (const Sal &other) { return r < other.r; } }; Sal a[n]; for (int i = 0; i < n; i++) { cin >> a[i].s >> a[i].q; a[i].r = 1. * a[i].s / a[i].q; a[i].idx = i; } sort(a, a + n); long long cur = 0; priority_queue< array<int, 2> > pq; pair<int, double> res = {0, -w}; int j = -1; for (int i = 0; i < n; i++) { pq.push({a[i].q, 0}); cur += a[i].q; while (a[i].r * cur > w) { cur -= pq.top()[0]; pq.pop(); } if (res < make_pair((int)pq.size(), -a[i].r * cur)) { res = {pq.size(), -a[i].r * cur}; j = i; } } cout << res.first << "\n"; while (!pq.empty()) { pq.pop(); } cur = 0; for (int i = 0; i <= j; i++) { pq.push({a[i].q, a[i].idx}); cur += a[i].q; while (a[i].r * cur > w) { cur -= pq.top()[0]; pq.pop(); } } while (!pq.empty()) { cout << 1 + pq.top()[1] << "\n"; pq.pop(); } return 0; }
Compilation message
# | 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 | 332 KB | Output is correct |
10 | Correct | 2 ms | 460 KB | Output is correct |
11 | Correct | 3 ms | 460 KB | Output is correct |
12 | Correct | 4 ms | 588 KB | Output is correct |
13 | Correct | 3 ms | 460 KB | Output is correct |
14 | Correct | 7 ms | 716 KB | Output is correct |
15 | Correct | 8 ms | 716 KB | Output is correct |
# | 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 | 0 ms | 204 KB | Output is correct |
4 | Correct | 8 ms | 912 KB | Output is correct |
5 | Correct | 21 ms | 2124 KB | Output is correct |
6 | Correct | 156 ms | 8912 KB | Output is correct |
7 | Correct | 212 ms | 11980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 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 | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 3632 KB | Output is correct |
2 | Correct | 61 ms | 3616 KB | Output is correct |
3 | Correct | 58 ms | 3604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 6148 KB | Output is correct |
2 | Correct | 92 ms | 6152 KB | Output is correct |
3 | Correct | 90 ms | 6084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 241 ms | 13320 KB | Output is correct |
2 | Correct | 248 ms | 13408 KB | Output is correct |
3 | Correct | 240 ms | 13240 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 283 ms | 15112 KB | Output is correct |
2 | Correct | 295 ms | 14976 KB | Output is correct |
3 | Correct | 279 ms | 15288 KB | Output is correct |