oj.uz

Submission #602913

# Submission time Handle Problem Language Result Execution time Memory
602913 2022-07-23T12:37:46 Z Joshc Hiring (IOI09_hiring) C++11
100 / 100
 649 ms 13196 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

ll s[500005], q[500005], w, t = 0, opt = 0;
pair<int, ld> best = {0, 0};

bool comp(int x, int y) {
    return s[x]*q[y] < s[y]*q[x];
}

struct comp2 {
    bool operator() (int a, int b) {
        return q[a] < q[b];
    }
};

priority_queue<int, vector<int>, comp2> pq;

void process(int x, int r) {
    t += q[x];
    pq.push(x);
    while (t*s[x] > w*q[x]) {
        t -= q[pq.top()];
        pq.pop();
    }
    pair<int, ld> cur = make_pair(pq.size(), -1.0*t*s[x]/q[x]);
    if (cur > best) {
        best = cur;
        opt = r;
    }
}

int main() {
    int n;
    scanf("%d%lld", &n, &w);
    vector<int> v;
    for (int i=1; i<=n; i++) {
        scanf("%lld%lld", &s[i], &q[i]);
        v.push_back(i);
    }
    sort(v.begin(), v.end(), comp);
    for (int i=1; i<=n; i++) process(v[i-1], i);
    printf("%d\n", best.first);
    while (!pq.empty()) pq.pop();
    t = 0;
    for (int i=1; i<=opt; i++) process(v[i-1], i);
    while (!pq.empty()) {
        printf("%d\n", pq.top());
        pq.pop();
    }
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%lld", &n, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld%lld", &s[i], &q[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 4 ms 524 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 7 ms 628 KB Output is correct
15 Correct 7 ms 596 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 11 ms 852 KB Output is correct
5 Correct 29 ms 1948 KB Output is correct
6 Correct 277 ms 7664 KB Output is correct
7 Correct 334 ms 10644 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3068 KB Output is correct
2 Correct 89 ms 3184 KB Output is correct
3 Correct 90 ms 3076 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5364 KB Output is correct
2 Correct 158 ms 5416 KB Output is correct
3 Correct 148 ms 5380 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 11780 KB Output is correct
2 Correct 571 ms 11796 KB Output is correct
3 Correct 446 ms 11820 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 13172 KB Output is correct
2 Correct 566 ms 13196 KB Output is correct
3 Correct 649 ms 13172 KB Output is correct