Submission #602913

#	Time	Username	Problem	Language	Result	Execution time	Memory
602913		Joshc	Hiring (IOI09_hiring)	C++11	100 / 100	649 ms	13196 KiB

hiring

#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 (stderr)

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 / 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