oj.uz

Submission #399406

# Submission time Handle Problem Language Result Execution time Memory
399406 2021-05-05T16:59:23 Z AugustinasJucas Hiring (IOI09_hiring) C++14
100 / 100
 635 ms 38676 KB 
#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 <= 1; 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(), -(long double) sm * y.first), make_pair(i1, i2)));
            i2++;
        }
  //      cout <<  ", po jo mx = " << mx.first.first << "\n\n";
        i1++;
        break;
    }
    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;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:15:13: warning: unused variable 'sq' [-Wunused-variable]
   15 |         int sq = sqrt(q);
      |             ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 4 ms 1100 KB Output is correct
11 Correct 5 ms 1100 KB Output is correct
12 Correct 6 ms 1356 KB Output is correct
13 Correct 6 ms 1228 KB Output is correct
14 Correct 10 ms 1736 KB Output is correct
15 Correct 11 ms 1608 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 15 ms 1988 KB Output is correct
5 Correct 35 ms 4288 KB Output is correct
6 Correct 292 ms 20528 KB Output is correct
7 Correct 311 ms 29944 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8072 KB Output is correct
2 Correct 98 ms 8064 KB Output is correct
3 Correct 99 ms 8056 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 15036 KB Output is correct
2 Correct 136 ms 16120 KB Output is correct
3 Correct 137 ms 14972 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 35416 KB Output is correct
2 Correct 426 ms 35480 KB Output is correct
3 Correct 391 ms 33356 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 38376 KB Output is correct
2 Correct 635 ms 38552 KB Output is correct
3 Correct 581 ms 38676 KB Output is correct