oj.uz

Submission #456354

# Submission time Handle Problem Language Result Execution time Memory
456354 2021-08-06T13:49:13 Z chunghan Hiring (IOI09_hiring) C++17
100 / 100
 471 ms 23600 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

ll N, W, sum, rst, im;
double psum = 1e18;
pair<pair<ll, ll>, int> D[500005];
pair<pair<ll, ll>, int> max_k;
priority_queue<pair<pair<ll, ll>, int>> pq;

bool cmp(pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b) {
    pair<ll, ll> x = a.first, y = b.first;
    return x.first * y.second > y.first * x.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        int q, s;
        cin >> s >> q;
        D[i] = {{q, s}, i};
    }
    sort(D, D+N, cmp);
    for (int i = 0; i < N; i++) {
        pair<ll, ll> E = D[i].first;
        ll Q = E.first, S = E.second;
        pq.push(D[i]);
        sum += Q;
        while ((double)sum/Q*S > W && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (rst < (ll)pq.size()) {
            rst = pq.size();
            psum = (double)sum*S/Q;
            max_k = D[i];
            im = i;
        } else if (rst == (ll)pq.size()) {
            if ((double)sum/Q*S < psum) {
                psum = (double)sum*S/Q;
                max_k = D[i];
                im = i;
            }
        }
    }
    sum = 0;
    ll Qr = max_k.first.first, Sr = max_k.first.second;
    if (rst == 0) {
        cout << 0 <<endl;
        return 0;
    }
    while(!pq.empty()) pq.pop();
    for (int i = 0; i < N; i++) {
        pair<ll, ll> E = D[i].first;
        ll Q = E.first, S = E.second;
        pq.push(D[i]);
        sum += Q;
        while ((double)sum/Q*S > W && !pq.empty()) {
            sum -= pq.top().first.first;
            pq.pop();
        }
        if (i == im) {
            cout << pq.size() << '\n';
            while (!pq.empty()) {
                cout << pq.top().second + 1 << '\n';
                pq.pop();
            }
            break;
        }
    }
    return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:51:8: warning: unused variable 'Qr' [-Wunused-variable]
   51 |     ll Qr = max_k.first.first, Sr = max_k.first.second;
      |        ^~
hiring.cpp:51:32: warning: unused variable 'Sr' [-Wunused-variable]
   51 |     ll Qr = max_k.first.first, Sr = max_k.first.second;
      |                                ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 416 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 6 ms 780 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 9 ms 872 KB Output is correct
15 Correct 10 ms 972 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 14 ms 1156 KB Output is correct
5 Correct 37 ms 2332 KB Output is correct
6 Correct 254 ms 10536 KB Output is correct
7 Correct 347 ms 15956 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4608 KB Output is correct
2 Correct 95 ms 5784 KB Output is correct
3 Correct 93 ms 5780 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8168 KB Output is correct
2 Correct 155 ms 10176 KB Output is correct
3 Correct 154 ms 10168 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 17248 KB Output is correct
2 Correct 397 ms 22036 KB Output is correct
3 Correct 399 ms 21916 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 18236 KB Output is correct
2 Correct 458 ms 23600 KB Output is correct
3 Correct 450 ms 23580 KB Output is correct