#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;
pair <int, int> res;
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;
}
int get(int node, int l, int r, int val){
if (l==r)
return min(val/l,st[node].cnt);
int mid=(l+r)>>1;
return (st[node<<1].sum<val?st[node<<1].cnt+get(node<<1|1,mid+1,r,val-st[node<<1].sum):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)
res=max(res,{get(1,1,20000,lim)+1,-j});
update(1,1,20000,q[i]);
}
res.second=-res.second;
cout << res.first << '\n';
int j=a[res.second],lim=w*q[j]/s[j]-q[j];
sort(a+1,a+res.second,[](int i, int j){return q[i]<q[j];});
for (int i=1;i<res.second;i++){
lim-=q[a[i]];
if (lim<0)
break;
cout << a[i] << '\n';
}
cout << j << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
2 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
5 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
6 |
Partially correct |
2 ms |
6748 KB |
Partially correct |
7 |
Partially correct |
1 ms |
6492 KB |
Partially correct |
8 |
Partially correct |
2 ms |
6492 KB |
Partially correct |
9 |
Correct |
3 ms |
6748 KB |
Output is correct |
10 |
Partially correct |
2 ms |
6748 KB |
Partially correct |
11 |
Correct |
3 ms |
6748 KB |
Output is correct |
12 |
Partially correct |
3 ms |
6492 KB |
Partially correct |
13 |
Partially correct |
4 ms |
6748 KB |
Partially correct |
14 |
Correct |
6 ms |
7004 KB |
Output is correct |
15 |
Partially correct |
7 ms |
7004 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Partially correct |
1 ms |
6540 KB |
Partially correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Partially correct |
9 ms |
7004 KB |
Partially correct |
5 |
Partially correct |
20 ms |
10900 KB |
Partially correct |
6 |
Correct |
132 ms |
13716 KB |
Output is correct |
7 |
Partially correct |
153 ms |
14208 KB |
Partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
6748 KB |
Partially correct |
2 |
Partially correct |
1 ms |
6748 KB |
Partially correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Partially correct |
1 ms |
6748 KB |
Partially 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 |
Partially correct |
1 ms |
6748 KB |
Partially correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
51 ms |
13396 KB |
Partially correct |
2 |
Partially correct |
51 ms |
13400 KB |
Partially correct |
3 |
Correct |
55 ms |
13396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
73 ms |
13484 KB |
Partially correct |
2 |
Partially correct |
73 ms |
13464 KB |
Partially correct |
3 |
Correct |
73 ms |
13480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
14040 KB |
Output is correct |
2 |
Partially correct |
202 ms |
14164 KB |
Partially correct |
3 |
Correct |
186 ms |
14164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
14488 KB |
Output is correct |
2 |
Partially correct |
228 ms |
14492 KB |
Partially correct |
3 |
Correct |
218 ms |
14416 KB |
Output is correct |