This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <string>
#include <numeric>
using namespace std;
using ll = long long;
struct segtree
{
int n;
vector<ll> sum;
vector<int> counter;
segtree(int n) : n(n)
{
sum.resize(4 * n + 5);
counter.resize(4 * n + 5);
}
void update(int p, int l, int r, int v)
{
if (l > r) return;
if (l == r)
{
sum[v] += p;
++counter[v];
return;
}
int m = (l + r) >> 1;
if (p <= m) update(p, l, m, v << 1);
else update(p, m + 1, r, v << 1 | 1);
sum[v] = sum[v << 1] + sum[v << 1 | 1];
counter[v] = counter[v << 1] + counter[v << 1 | 1];
}
void update(int p)
{
update(p, 0, n - 1, 1);
}
//first h such that first h have sum > possible
int get(ll w, ll s, int l, int r, int v)
{
if (l > r || sum[v] * s <= w) return -1;
if (l == r)
{
//c * s > w
//c > w / s
return w / (s * (sum[v] / counter[v])) + 1;
}
int m = (l + r) >> 1;
if (sum[v << 1] * s > w) return get(w, s, l, m, v << 1);
return counter[v << 1] + get(w - sum[v << 1] * s, s, m + 1, r, v << 1 | 1);
}
int get(ll w, ll s)
{
return get(w, s, 0, n - 1, 1);
}
ll getSum(int h, int l, int r, int v)
{
if (l > r || h == 0) return 0;
if (l == r) return h * (sum[v] / counter[v]);
int m = (l + r) >> 1;
if (counter[v << 1] >= h) return getSum(h, l, m, v << 1);
else return sum[v << 1] + getSum(h - counter[v << 1], m + 1, r, v << 1 | 1);
}
ll getSum(int h)
{
return getSum(h, 0, n - 1, 1);
}
};
struct best
{
int i;
int h;
ll n, d;
best(int i, int h, ll n, ll d) : i(i), h(h), n(n), d(d)
{}
friend bool operator<(best b, best a)
{
if (b.h < a.h) return true;
if (b.h > a.h) return false;
return b.n * a.d < b.d * a.n;
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
ll w;
cin >> n >> w;
vector<ll> s(n), q(n);
for (int i = 0; i < n; ++i) cin >> s[i] >> q[i];
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0);
sort(inds.begin(), inds.end(), [&s, &q](int i, int j){ return s[i] * q[j] < s[j] * q[i]; });
best res{0, 0, 0, 1};
segtree ds(20001);
for (int i = 0; i < inds.size(); ++i)
{
ds.update(q[inds[i]]);
int h = ds.get(w * q[inds[i]], s[inds[i]]);
if (h == -1) h = i + 2;
--h;
ll sum = ds.getSum(h);
res = max(res, {i, h, sum * s[inds[i]], q[inds[i]]});
}
cout << res.h;
return 0;
}
/*
4 100
5 1000
10 100
8 10
20 1
*/
/*
3 4
1 2
1 3
1 3
*/
/*
3 40
10 1
10 2
10 3
*/
Compilation message (stderr)
hiring.cpp: In function 'int main()':
hiring.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int i = 0; i < inds.size(); ++i)
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |