# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1109242 | dsyz | Hiring (IOI09_hiring) | C++17 | 1571 ms | 45212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define MAXN (1000005)
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll N;
ld W;
cin>>N>>W;
ld S[N], Q[N]; //min salary, qualification
pair<pair<ld,ld>,ld> arr[N];
for(ll i = 0;i < N;i++){
cin>>S[i]>>Q[i];
arr[i] = {{Q[i],S[i]},i};
}
sort(arr,arr + N);
//I am guessing the wages for all other workers will resolve around one worker's exact minimum salary S[i]
vector<ll> ans;
ld spent = 1e18;
for(ll strictest = 0;strictest < N;strictest++){
ld budget = W;
vector<ll> cur;
if(arr[strictest].first.second > budget){
continue;
}
budget -= arr[strictest].first.second;
ll ind = arr[strictest].second;
cur.push_back(ind + 1);
for(ll i = 0;i < strictest;i++){
ld needed = (arr[i].first.first / arr[strictest].first.first) * arr[strictest].first.second;
ll ind = arr[i].second;
if(needed >= arr[i].first.second && budget >= needed){
budget -= needed;
cur.push_back(ind + 1);
}
}
for(ll i = strictest + 1;i < N;i++){
ld needed = (arr[i].first.first / arr[strictest].first.first) * arr[strictest].first.second;
ll ind = arr[i].second;
/*if(strictest == 1){
cout<<"DEBUG1: "<<'\n';
cout<<"NEEDED: "<<'\n';
}*/
if(needed >= arr[i].first.second && budget >= needed){
budget -= needed;
cur.push_back(ind + 1);
}
}
/*if(strictest == 1){
cout<<"DEBUG2: "<<'\n';
cout<<"CURSIZE: "<<cur.size()<<'\n';
for(ll i = 0;i < cur.size();i++){
cout<<cur[i]<<" ";
}
cout<<'\n';
cout<<"SPENT: "<<W - budget<<'\n';
}*/
//cout<<"WORKER: "<<arr[strictest].first.second<<" "<<arr[strictest].first.first<<" "<<arr[strictest].second<<'\n';
if(cur.size() > ans.size()){
spent = W - budget;
ans = cur;
}else if(cur.size() == ans.size() && (W - budget) <= spent){
spent = W - budget;
ans = cur;
}
}
cout<<ans.size()<<'\n';
for(ll i = 0;i < ans.size();i++){
cout<<ans[i]<<'\n';
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |