fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.  
  45.     ll* facs = new ll[MX];
  46.     ll* facInvs = new ll[MX];
  47.  
  48.     ll choose(ll a, ll b) {
  49.         if (b > a) return 0;
  50.         if (a < 0) return 0;
  51.         if (b < 0) return 0;
  52.         ll cur = facs[a];
  53.         cur = mul(cur, facInvs[b]);
  54.         cur = mul(cur, facInvs[a-b]);
  55.         return cur;
  56.     }
  57.  
  58.     void initFacs() {
  59.         facs[0] = 1; 
  60.         facInvs[0] = 1;
  61.         for (int i = 1 ; i < MX ; i ++ ) {
  62.             facs[i] = (facs[i-1] * i) % MOD;
  63.             facInvs[i] = inv(facs[i]);
  64.         }
  65.     }
  66.     int main()  {
  67.         ios_base::sync_with_stdio(0); cin.tie(0);  
  68.         int t ; cin >> t; 
  69.         const int LIMIT = 6500000;              // sieve up to ~6.5 million
  70.         const int TARGET = 400000;              // need first 400 000 primes
  71.  
  72.         vector<bool> is_composite(LIMIT+1, false);
  73.         vector<int> primes;
  74.  
  75.         primes.reserve(TARGET);
  76.         is_composite[0] = is_composite[1] = true;
  77.  
  78.         for (int x = 2; x <= LIMIT; x++) {
  79.             if (!is_composite[x]) {
  80.                 primes.push_back(x);
  81.                 if ((int)primes.size() == TARGET) break;
  82.                 if ((long long)x * x <= LIMIT) {
  83.                     for (int y = x * x; y <= LIMIT; y += x) {
  84.                         is_composite[y] = true;
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.  
  90.  
  91.         vector<ll> pref(primes.size() + 1,0);
  92.         for (int i = 0  ; i < primes.size() ; i ++) {
  93.             pref[i + 1] = pref[i] + primes[i]; 
  94.         }
  95.         while (t --) {
  96.             int n ; cin >> n; 
  97.             vector<int> arr(n);
  98.             for (int i =  0 ; i < n; i ++) {
  99.                 cin >> arr[i]; 
  100.             }
  101.             ll sum = 0;
  102.             for (int i = 0 ; i < n ; i ++ ) {
  103.                 sum += arr[i]; 
  104.             }
  105.             sort(arr.begin(), arr.end(),greater<int>()); 
  106.             int res = 0;
  107.             int curr = n;
  108.             int p = n - 1;
  109.             while (pref[curr] > sum ) {
  110.                 res ++; 
  111.                 sum -= arr[p];
  112.                 p --; 
  113.                 curr --;             
  114.             } 
  115.             cout << res << endl;
  116.         }
  117.  
  118.         return 0;
  119.     }
  120.  
Success #stdin #stdout 0.07s 8636KB
comments (?)
stdin
copy 
5
3
5 5 5
4
2 3 2 4
1
3
3
2 100 2
5
2 4 2 11 2
stdout
copy 
0
2
0
0
1
https://ideone.com/zWvIOH
language:
C++ (gcc 8.3)
created:
2 days 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!