oj.uz

Submission #297659

# Submission time Handle Problem Language Result Execution time Memory
297659 2020-09-11T17:28:53 Z hhh07 Hiring (IOI09_hiring) C++14
100 / 100
 1016 ms 35228 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 416 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 9 ms 768 KB Output is correct
10 Correct 10 ms 896 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 20 ms 1024 KB Output is correct
13 Correct 11 ms 1024 KB Output is correct
14 Correct 26 ms 1436 KB Output is correct
15 Correct 24 ms 1276 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 36 ms 1660 KB Output is correct
5 Correct 81 ms 5228 KB Output is correct
6 Correct 544 ms 20036 KB Output is correct
7 Correct 764 ms 29888 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 9184 KB Output is correct
2 Correct 218 ms 9184 KB Output is correct
3 Correct 205 ms 9272 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 16212 KB Output is correct
2 Correct 364 ms 16084 KB Output is correct
3 Correct 367 ms 16092 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 32060 KB Output is correct
2 Correct 843 ms 31784 KB Output is correct
3 Correct 835 ms 31812 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 35092 KB Output is correct
2 Correct 1008 ms 35228 KB Output is correct
3 Correct 996 ms 35136 KB Output is correct