fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. main()
  7. {
  8.     int t;
  9.     cin >> t;
  10.     while (t--)
  11.     {
  12.         ll n, sum = 0, cost;
  13.         cin >> n >> cost;
  14.         vector<ll> v(n), pref(n - 1, 0);
  15.         for (auto &it : v)
  16.             cin >> it, sum += it;
  17.         sort(v.begin() + 1, v.end());
  18.         ll m=0;
  19.         for(int i=1;i<n;i++){
  20.             m+=v[0]*v[i];
  21.             if(m>cost) break;
  22.         }
  23.         if(m<=cost){
  24.             cout<<1<<"\n";
  25.             return 0;
  26.         }
  27.         pref[0] = v[1];
  28.         for (int i = 1; i < n - 1; i++)
  29.         {
  30.             pref[i] = v[i + 1] + pref[i - 1];
  31.         }
  32.         ll cnt = n;
  33.         for (int i = 1; i < n; i++)
  34.         {
  35.             if (pref[i - 1] * (sum - pref[i - 1]) <= cost)
  36.                 cnt--;
  37.             else if (((pref[n - 2] - pref[n - 2 - i]) * (sum - (pref[n - 2] - pref[n - 2 - i])))<=cost)
  38.                 cnt--;
  39.             else
  40.                 break;
  41.         }
  42.         cout << cnt << "\n";
  43.     }
  44. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
3 1000000000000000000
2000000 4000000 5000000
4 150
100 1 1 1
6 1275
35 15 10 25 10 5
6 400
35 15 10 25 10 5
stdout
copy 
1
https://ideone.com/yjZGSM
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!