Submission #297659

#	Time	Username	Problem	Language	Result	Execution time	Memory
297659		hhh07	Hiring (IOI09_hiring)	C++14	100 / 100	1016 ms	35228 KiB

hiring

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<double, double> ii;
typedef pair<ii, ii> iiii;


int main(){
    ios_base::sync_with_stdio(false);
    double n, w;
    cin >> n >> w;
    vector<iiii> c; double s, q;
    for (int i = 0; i < n; i++){
        cin >> s >> q;
        c.push_back({{s/q, i}, {s, q}});
    }
    
    sort(c.begin(), c.end());
    double maxi = 0, cost = INT_MAX, idx;
    double uk = 0; priority_queue<double> pq;
    for (int i = 0; i < n; i++){
        pq.push(c[i].second.second);
        uk += c[i].second.second;
        double maks = w/c[i].first.first;
        while(uk > maks){
            uk -= pq.top();
            pq.pop();
        }
        double cijena = uk*c[i].first.first;
        if (pq.size() > maxi || (pq.size() == maxi && cijena < cost)){
            maxi = pq.size();
            cost = cijena;
            idx = i;
        }
    }
    priority_queue<ii> ans; uk = 0;
    for (int i = 0; i <= idx; i++){
        ans.push({c[i].second.second, c[i].first.second});
        uk += c[i].second.second;
    }
    double maks = w/c[idx].first.first;
    
    while(uk > maks){
        uk -= ans.top().first;
        ans.pop();
    }
    vector<int> x;
    while(!ans.empty()){
        x.push_back(ans.top().second);
        ans.pop();
    }
    cout << x.size() << endl;
    for (int i = 0; i < x.size(); i++){
        cout << x[i] + 1 << endl;
    }
    return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < x.size(); i++){
      |                     ~~^~~~~~~~~~
hiring.cpp:48:26: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     double maks = w/c[idx].first.first;
      |                          ^

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