# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
623024 |
2022-08-05T05:32:07 Z |
sofapuden |
Hiring (IOI09_hiring) |
C++14 |
|
671 ms |
39288 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct T{
ll a, b, i;
};
bool cmp(T a, T b){
return a.a*b.b < b.a*a.b;
}
void solve(){
ll n, w; cin >> n >> w;
vector<T> A(n);
for(int i = 0; i < n; ++i)cin >> A[i].a >> A[i].b, A[i].i = i+1;
sort(A.begin(),A.end(),cmp);
vector<pair<ll,ll>> v(n);
for(int i = 0; i < n; ++i)v[i] = {A[i].a,A[i].b};
ll su = 0;
ll cn = 0;
pair<ll,ll> mn = {0,0};
multiset<ll> cur;
set<pair<ll,ll>> in;
for(int i = 0; i < n; ++i){
su+=v[i].second;
cur.insert(v[i].second);
while(su*v[i].first > w * v[i].second){
su-=*prev(cur.end());
cur.erase(prev(cur.end()));
}
if(cn == cur.size()){
if(mn.first*v[i].second > su*v[i].first*mn.second){
mn = {su*v[i].first,v[i].second};
}
}
if(cn < cur.size()){
cn = cur.size();
mn = {su*v[i].first,v[i].second};
}
}
cout << cn << '\n';
su = 0;
for(int i = 0; i < n; ++i){
su+=v[i].second;
in.insert({v[i].second,i});
while(su*v[i].first > w * v[i].second){
su-=prev(in.end())->first;
in.erase(prev(in.end()));
}
if(in.size() == cn && mn == make_pair(su*v[i].first,v[i].second)){
for(auto x : in)cout << A[x.second].i << '\n';
return;
}
}
}
int main(){
solve();
}
Compilation message
hiring.cpp: In function 'void solve()':
hiring.cpp:34:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(cn == cur.size()){
| ~~~^~~~~~~~~~~~~
hiring.cpp:39:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if(cn < cur.size()){
| ~~~^~~~~~~~~~~~
hiring.cpp:53:16: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
53 | if(in.size() == cn && mn == make_pair(su*v[i].first,v[i].second)){
| ~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
304 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 |
224 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
440 KB |
Output is correct |
8 |
Correct |
2 ms |
404 KB |
Output is correct |
9 |
Correct |
4 ms |
596 KB |
Output is correct |
10 |
Correct |
4 ms |
596 KB |
Output is correct |
11 |
Correct |
5 ms |
700 KB |
Output is correct |
12 |
Correct |
7 ms |
1108 KB |
Output is correct |
13 |
Correct |
8 ms |
724 KB |
Output is correct |
14 |
Correct |
11 ms |
1236 KB |
Output is correct |
15 |
Correct |
13 ms |
1328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
20 ms |
1768 KB |
Output is correct |
5 |
Correct |
51 ms |
4364 KB |
Output is correct |
6 |
Correct |
359 ms |
22168 KB |
Output is correct |
7 |
Correct |
384 ms |
30312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
8676 KB |
Output is correct |
2 |
Correct |
117 ms |
8688 KB |
Output is correct |
3 |
Correct |
126 ms |
8728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
14952 KB |
Output is correct |
2 |
Correct |
164 ms |
14960 KB |
Output is correct |
3 |
Correct |
175 ms |
14956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
478 ms |
33860 KB |
Output is correct |
2 |
Correct |
477 ms |
33888 KB |
Output is correct |
3 |
Correct |
491 ms |
33904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
652 ms |
39104 KB |
Output is correct |
2 |
Correct |
639 ms |
39288 KB |
Output is correct |
3 |
Correct |
671 ms |
39252 KB |
Output is correct |