#include <bits/stdc++.h>
#define int long long
using namespace std;
struct T{
int sum,cnt;
}st[80001];
int n,s[500001],q[500001],a[500001],w,res,num,den,pos;
void update(int node, int l, int r, int i){
if (l>i||r<i)
return;
if (l==r){
st[node].sum+=l;
st[node].cnt++;
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,i);
update(node<<1|1,mid+1,r,i);
st[node].sum=st[node<<1].sum+st[node<<1|1].sum;
st[node].cnt=st[node<<1].cnt+st[node<<1|1].cnt;
}
pair <int, int> get(int node, int l, int r, int val){
if (l==r){
int x=min(val/l,st[node].cnt);
return {x,l*x};
}
int mid=(l+r)>>1;
if (st[node<<1].sum<val){
auto [x,y]=get(node<<1|1,mid+1,r,val-st[node<<1].sum);
x+=st[node<<1].cnt;
y+=st[node<<1].sum;
return {x,y};
}
return get(node<<1,l,mid,val);
}
int32_t main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> w;
for (int i=1;i<=n;i++)
cin >> s[i] >> q[i];
iota(a,a+n+1,0);
sort(a+1,a+n+1,[](int i, int j){return s[i]*q[j]<s[j]*q[i];});
for (int j=1;j<=n;j++){
int i=a[j];
int lim=w*q[i]/s[i]-q[i];
if (lim>=0){
auto [x,y]=get(1,1,20000,lim);
x++;
y=(y+q[i])*s[i];
if (res<x||(res==x&&y*den<num*q[i])){
res=x;
num=y;
den=q[i];
pos=j;
}
}
update(1,1,20000,q[i]);
}
cout << res << '\n';
int j=a[pos],lim=w*q[j]/s[j]-q[j];
sort(a+1,a+pos,[](int i, int j){return q[i]<q[j];});
for (int i=1;i<pos;i++){
lim-=q[a[i]];
if (lim<0)
break;
cout << a[i] << '\n';
}
cout << j << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6492 KB |
Output is correct |
9 |
Correct |
3 ms |
6748 KB |
Output is correct |
10 |
Correct |
3 ms |
6748 KB |
Output is correct |
11 |
Correct |
3 ms |
6748 KB |
Output is correct |
12 |
Correct |
5 ms |
6492 KB |
Output is correct |
13 |
Correct |
4 ms |
6748 KB |
Output is correct |
14 |
Correct |
7 ms |
7000 KB |
Output is correct |
15 |
Correct |
7 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
9 ms |
7004 KB |
Output is correct |
5 |
Correct |
20 ms |
10844 KB |
Output is correct |
6 |
Correct |
152 ms |
13788 KB |
Output is correct |
7 |
Correct |
175 ms |
14164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6876 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
13208 KB |
Output is correct |
2 |
Correct |
57 ms |
13392 KB |
Output is correct |
3 |
Correct |
56 ms |
13392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
13444 KB |
Output is correct |
2 |
Correct |
90 ms |
13524 KB |
Output is correct |
3 |
Correct |
74 ms |
13436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
240 ms |
14208 KB |
Output is correct |
2 |
Correct |
209 ms |
14232 KB |
Output is correct |
3 |
Correct |
195 ms |
14160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
14560 KB |
Output is correct |
2 |
Correct |
237 ms |
14676 KB |
Output is correct |
3 |
Correct |
267 ms |
14496 KB |
Output is correct |