# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
748778 | 2023-05-27T02:05:06 Z | jamielim | Hiring (IOI09_hiring) | C++14 | 307 ms | 15876 KB |
#include <bits/stdc++.h> using namespace std; int n; long long w; pair<pair<double,int>,int> p[500005]; int main() { scanf("%d%lld",&n,&w); int s,q; for(int i=0;i<n;i++){ scanf("%d%d",&s,&q); p[i].first=make_pair((double)s/(double)q,q); p[i].second=i+1; } sort(p,p+n); int ans=0; priority_queue<int> pq; long long sum=0; double price=w; for(int i=0;i<n;i++){ sum+=p[i].first.second; pq.push(p[i].first.second); double v=p[i].first.first; while(!pq.empty()&&sum>w/v){ sum-=pq.top(); pq.pop(); } if(ans<(int)pq.size()){ ans=(int)pq.size(); price=sum*v; }else if(ans==(int)pq.size()){ price=min(price,sum*v); } } printf("%d\n",ans); sum=0; priority_queue<pair<int,int> > pq2; for(int i=0;i<n;i++){ sum+=p[i].first.second; pq2.push(make_pair(p[i].first.second,p[i].second)); double v=p[i].first.first; while(!pq2.empty()&&sum>w/v){ sum-=pq2.top().first; pq2.pop(); } //printf("%d %d %f %f\n",ans,(int)pq2.size(),price,sum*v); if(ans==(int)pq2.size()&&abs(price-sum*v)<1e-8){ while(!pq2.empty()){ printf("%d\n",pq2.top().second); pq2.pop(); } break; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 2 ms | 340 KB | Output is correct |
10 | Correct | 3 ms | 468 KB | Output is correct |
11 | Correct | 3 ms | 468 KB | Output is correct |
12 | Correct | 6 ms | 596 KB | Output is correct |
13 | Correct | 4 ms | 512 KB | Output is correct |
14 | Correct | 6 ms | 724 KB | Output is correct |
15 | Correct | 7 ms | 788 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 12 ms | 900 KB | Output is correct |
5 | Correct | 25 ms | 2232 KB | Output is correct |
6 | Correct | 171 ms | 9300 KB | Output is correct |
7 | Correct | 224 ms | 12580 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 3768 KB | Output is correct |
2 | Correct | 66 ms | 3756 KB | Output is correct |
3 | Correct | 71 ms | 3796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 6424 KB | Output is correct |
2 | Correct | 109 ms | 6372 KB | Output is correct |
3 | Correct | 105 ms | 6388 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 265 ms | 13916 KB | Output is correct |
2 | Correct | 259 ms | 13888 KB | Output is correct |
3 | Correct | 263 ms | 13956 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 307 ms | 15860 KB | Output is correct |
2 | Correct | 286 ms | 15876 KB | Output is correct |
3 | Correct | 285 ms | 15804 KB | Output is correct |