#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pld = pair<ll, double>;
#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
const int MXN = 5e5+5;
int n, S[MXN], Q[MXN], cnt[MXN<<2], sum[MXN<<2], ordq[MXN], posq[MXN], ordsq[MXN];
ll W;
void upd(int p, int l=1, int r=n+2, int id=1) {
if(r-l == 1) {
cnt[id] = 1;
sum[id] = Q[ordq[l]];
return;
}
p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
cnt[id] = cnt[lc] + cnt[rc];
sum[id] = sum[lc] + sum[rc];
}
pld val;
int get(int i, int l=1, int r=n+2, int id=1) {
if(r-l == 1) return l;
if((1ll*(int(val.Y)+sum[lc])*S[i]+Q[i]-1)/Q[i]<=W) {
val.X += cnt[lc];
val.Y += sum[lc];
return get(i, mid, r, rc);
}
return get(i, l, mid, lc);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> W;
for(int i=1; i<=n; i++) cin >> S[i] >> Q[i];
iota(ordq+1, ordq+n+1, 1);
sort(ordq+1, ordq+n+1, [&](int i, int j) {
return Q[i] < Q[j];
});
for(int i=1; i<=n; i++) posq[ordq[i]] = i;
iota(ordsq+1, ordsq+n+1, 1);
sort(ordsq+1, ordsq+n+1, [&](int i, int j) {
return S[i]*Q[j] < S[j]*Q[i];
});
pld ans = {0, 0};
pii wh = {0, 0};
for(int i=1; i<=n; i++) {
upd(posq[ordsq[i]]);
val = {0, 0};
int r = get(ordsq[i]);
val.Y = -val.Y * double(S[ordsq[i]]) / double(Q[ordsq[i]]);
if(val>ans) {
ans = val;
wh = {i, r};
}
}
cout << ans.X << '\n';
for(int i=1; i<=wh.X; i++)
if(posq[ordsq[i]]<wh.Y)
cout << ordsq[i] << '\n';
return 0;
}
# | 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... |