# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
964988 | 2024-04-18T01:38:41 Z | fzyzzz_z | Hiring (IOI09_hiring) | C++17 | 541 ms | 21696 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fs first #define sc second int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll k; cin >> n >> k; vector<pair<int, int>> a(n); vector<int> ord(n); for (int i = 0; i < n; ++i) { cin >> a[i].sc >> a[i].fs; ord[i] = i; } sort(ord.begin(), ord.end(), [&](int & x, int & y){ if (a[x].fs * a[y].sc == a[x].sc * a[y].fs) return a[x].sc < a[y].sc; return (a[y].fs * a[x].sc <= a[y].sc * a[x].fs); }); set<pair<int, int>> st; int ans = 0, at = 0; ll cs = 0; ll tcb = 1, tct = 0; for (int i = 0; i < n; ++i) { int x = a[ord[i]].fs, y = a[ord[i]].sc; cs += x; st.insert({x, i}); while (cs * y > k * x) { pair<int, int> v = *st.rbegin(); cs -= v.fs; st.erase(v); } if (st.size() > ans) { ans = st.size(); tct = cs * y; tcb = x; at = i; } else if (cs * y * tcb < tct * x && st.size() == ans) { tct = cs * y; tcb = x; at = i; } } st.clear(); cs = 0; for (int i = 0; i < n; ++i) { int x = a[ord[i]].fs, y = a[ord[i]].sc; cs += x; st.insert({x, ord[i]}); while (cs * y > k * x) { pair<int, int> v = *st.rbegin(); cs -= v.fs; st.erase(v); } if (at == i) { cout << ans << "\n"; for (auto v: st) { cout << v.sc + 1 << "\n"; } return 0; } } assert(false); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 2 ms | 348 KB | Output is correct |
9 | Correct | 3 ms | 600 KB | Output is correct |
10 | Correct | 3 ms | 604 KB | Output is correct |
11 | Correct | 3 ms | 604 KB | Output is correct |
12 | Correct | 6 ms | 860 KB | Output is correct |
13 | Correct | 3 ms | 604 KB | Output is correct |
14 | Correct | 8 ms | 992 KB | Output is correct |
15 | Correct | 8 ms | 860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 10 ms | 1116 KB | Output is correct |
5 | Correct | 23 ms | 2356 KB | Output is correct |
6 | Correct | 233 ms | 12164 KB | Output is correct |
7 | Correct | 348 ms | 16796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 620 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 82 ms | 5052 KB | Output is correct |
2 | Correct | 82 ms | 4880 KB | Output is correct |
3 | Correct | 80 ms | 5040 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 125 ms | 8332 KB | Output is correct |
2 | Correct | 115 ms | 8456 KB | Output is correct |
3 | Correct | 117 ms | 8528 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 363 ms | 18372 KB | Output is correct |
2 | Correct | 394 ms | 18260 KB | Output is correct |
3 | Correct | 388 ms | 18256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 515 ms | 21696 KB | Output is correct |
2 | Correct | 463 ms | 21580 KB | Output is correct |
3 | Correct | 541 ms | 21688 KB | Output is correct |