Submission #399392

#	Time	Username	Problem	Language	Result	Execution time	Memory
399392		AugustinasJucas	Hiring (IOI09_hiring)	C++14	74 / 100	532 ms	65540 KiB

hiring

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int n;
long long w;

vector<pair<long 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);
        for(int i = 1; i <= sq; i++) {
            if(q % i != 0) continue;
            int sk = i;

            long double 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}, {0, 0}};
    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(), -(long 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 < mx.first.first; i++){
        cout << cur[i].second +1<< " ";
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6