Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define int long long
- #define mp make_pair
- #define pb push_back
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- using namespace std;
- using namespace __gnu_pbds;
- const int N = (int)3e5 + 111;
- const int md = (int)1e9 + 7;
- const int INF = (int)1e18;
- int a[N];
- int n,S;
- bool ok(int len){
- int sum = 0;
- int cur = 0;
- for(int i = 1; i <= len; i++){
- cur += a[i]*(i-1) - sum;
- sum += a[i];
- }
- if(cur <= S)
- return true;
- for(int i = len+1; i <= n; i++){
- cur -= sum - a[i-len]*len;
- sum -= a[i-len];
- cur += a[i]*(len-1)-sum;
- sum += a[i];
- if(cur <= S)
- return true;
- }
- return false;
- }
- void solve(){
- cin >> n >> S;
- for(int i = 1; i <= n; i++){
- cin >> a[i];
- }
- sort(a+1,a+n+1);
- int l = 1, r = n+1;
- while(r-l>1){
- int m = (l+r)>>1;
- if(ok(m))
- l = m;
- else
- r = m;
- }
- cout << l << "\n";
- return;
- }
- signed main(){
- ios::sync_with_stdio(false);cin.tie(nullptr);
- int tests = 1;
- // cin >> tests;
- for(int test = 1; test <= tests; test++){
- solve();
- }
- return 0;
- }
- /**
- k = 1
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement