# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
715370 | 2023-03-26T14:56:27 Z | Ahmed57 | Hiring (IOI09_hiring) | C++14 | 1232 ms | 63400 KB |
#include <bits/stdc++.h> using namespace std; signed main(){ long long n; long long w; cin>>n>>w; vector<pair<long double,pair<long double,long long>>> v; for(int i = 0;i<n;i++){ long double s,q;cin>>s>>q; v.push_back({s/q,{q,i+1}}); } sort(v.begin(),v.end()); priority_queue<pair<long double,int>> q,p; long double sum = 0; long long ma = 0,ind = -1; long double su = 0.0; for(int i = 0;i<v.size();i++){ p.push({-v[i].second.first,v[i].second.second}); sum+=(-p.top().first); q.push({-p.top().first,p.top().second}); p.pop(); long double no =sum*v[i].first; while(no>w){ pair<long double,int>pa = q.top(); q.pop(); sum-=pa.first; p.push({-pa.first,pa.second}); no =sum*v[i].first; } if(q.size()>ma){ ma=q.size(); ind = i; su = no; }if(q.size()==ma&&su>no){ su = no;ind =i; } } while(!q.empty())q.pop(); while(!p.empty())p.pop(); sum=0; for(int i = 0;i<=ind;i++){ p.push({-v[i].second.first,v[i].second.second}); sum+=(-p.top().first); q.push({-p.top().first,p.top().second}); p.pop(); long double no =sum*v[i].first; while(no>w){ pair<long double,int>pa = q.top(); q.pop(); sum-=pa.first; p.push({-pa.first,pa.second}); no =sum*v[i].first; } } cout<<q.size()<<endl; while(q.size()){ cout<<q.top().second<<"\n"; q.pop(); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 3 ms | 468 KB | Output is correct |
7 | Correct | 4 ms | 468 KB | Output is correct |
8 | Correct | 5 ms | 660 KB | Output is correct |
9 | Correct | 7 ms | 832 KB | Output is correct |
10 | Correct | 12 ms | 976 KB | Output is correct |
11 | Correct | 12 ms | 996 KB | Output is correct |
12 | Correct | 15 ms | 1232 KB | Output is correct |
13 | Correct | 16 ms | 1464 KB | Output is correct |
14 | Correct | 25 ms | 1964 KB | Output is correct |
15 | Correct | 27 ms | 2296 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 |
4 | Correct | 35 ms | 3156 KB | Output is correct |
5 | Correct | 113 ms | 7908 KB | Output is correct |
6 | Correct | 645 ms | 44028 KB | Output is correct |
7 | Correct | 878 ms | 53732 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 | 2 ms | 340 KB | Output is correct |
2 | Correct | 3 ms | 340 KB | Output is correct |
3 | Correct | 2 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 392 KB | Output is correct |
3 | Correct | 2 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 242 ms | 15740 KB | Output is correct |
2 | Correct | 266 ms | 15668 KB | Output is correct |
3 | Correct | 253 ms | 15656 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 474 ms | 28972 KB | Output is correct |
2 | Correct | 459 ms | 28772 KB | Output is correct |
3 | Correct | 436 ms | 28800 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1000 ms | 62120 KB | Output is correct |
2 | Correct | 1016 ms | 62108 KB | Output is correct |
3 | Correct | 1008 ms | 62032 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1202 ms | 63400 KB | Output is correct |
2 | Correct | 1232 ms | 63372 KB | Output is correct |
3 | Correct | 1154 ms | 63400 KB | Output is correct |