| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 399400 | AugustinasJucas | Hiring (IOI09_hiring) | C++14 | 0 ms | 0 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>
#pragma GCC optimize("O3")
using namespace std;
int n;
long long w;
vector<pair<double, pair<int, int> > > dals[20010];
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> w;
for(int j = 0; j < n; j++){
int s, q; cin >> s >> q;
int sq = sqrt(q);
int sk; long double kaina;
for(int i = 1; i <= sq; i++) {
if(q % i != 0) continue;
sk = i;
kaina = (1.0 * s) / (1.0 * (q/i));
dals[sk].push_back({kaina, {q/i, j}});
if(i * i == q) continue;
sk = q/i;
kaina = (1.0 * s) / (1.0 * i);
dals[sk].push_back({kaina, {i, j}});
}
}
pair<pair<int, long double>, pair<int, int> > mx = {{0 , 0}, {-1, -1}};
int i1 = 0;
for(auto &x : dals){
if(x.size() == 0){
i1++; continue;
}
sort(x.begin(), x.end());
multiset<int> cur; long long sm = 0;
int i2 = 0;
// cout << "darau " << i1 << endl;
// cout << "X: "; for(auto y : x) cout << y.second.first << " ";
// cout << endl;
for(auto y : x){
cur.insert(y.second.first);
sm += y.second.first;
while((long double) sm * y.first > w){
sm -= *cur.rbegin();
cur.erase(cur.find(*cur.rbegin()));
}
// cout << "po " << i2 << ", cure yra " << cur.size() << ", sm = " << sm << ", kaina = " << y.first << endl;
mx = max(mx, make_pair(make_pair((int)cur.size(), -(double) sm * y.first), make_pair(i1, i2)));
i2++;
}
// cout << ", po jo mx = " << mx.first.first << "\n\n";
i1++;
}
i1 = mx.second.first;
int i2 = mx.second.second;
vector<pair<int, int> > cur;
for(int i = 0; i <= i2; i++){
cur.push_back({(long double)dals[i1][i].second.first, dals[i1][i].second.second});
}
sort(cur.begin(), cur.end());
cout << mx.first.first << "\n";
for(int i = 0; i < min((int)cur.size(), mx.first.first); i++){
cout << cur[i].second +1<< " ";
}
return 0;
}