제출 #456343

#제출 시각아이디문제언어결과실행 시간메모리
456343chunghanHiring (IOI09_hiring)C++17
3 / 100
410 ms18292 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; ll N, W, sum, rst, psum = 1; pair<pair<ll, ll>, int> D[500005]; pair<pair<ll, ll>, int> max_k; priority_queue<pair<pair<ll, ll>, int>, vector<pair<pair<ll, ll>, int>>, less<pair<pair<ll, ll>, int>>> pq; bool cmp(pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b) { pair<ll, ll> x = a.first, y = b.first; return x.first * y.second > y.first * x.second; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> W; for (int i = 0; i < N; i++) { int q, s; cin >> s >> q; D[i] = {{q, s}, i}; } sort(D, D+N, cmp); for (int i = 0; i < N; i++) { pair<ll, ll> E = D[i].first; ll Q = E.first, S = E.second; pq.push(D[i]); sum += Q; while (sum*S > W*Q && !pq.empty()) { sum -= pq.top().first.first; pq.pop(); } if (rst < (ll)pq.size()) { rst = pq.size(); psum = sum; max_k = D[i]; } else if (rst == (ll)pq.size()) { if (sum*S*max_k.first.first < (double)psum*max_k.first.second*Q) { psum = sum; max_k = D[i]; } } } cout << rst << '\n'; sum = 0; int cnt = 0; ll Qr = max_k.first.first, Sr = max_k.first.second, im = max_k.second; if (Qr == 0 && Sr == 0) return 0; while(!pq.empty()) pq.pop(); for (int i = 0; i < N; i++) { pair<ll, ll> E = D[i].first; ll Q = E.first, S = E.second; pq.push(D[i]); sum += Q; while (sum*S > W*Q && !pq.empty()) { sum -= pq.top().first.first; pq.pop(); } if (i == im) { while (!pq.empty()) { cout << pq.top().second + 1 << '\n'; pq.pop(); } break; } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

hiring.cpp: In function 'int main()':
hiring.cpp:49:9: warning: unused variable 'cnt' [-Wunused-variable]
   49 |     int cnt = 0;
      |         ^~~
#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...