fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3*/
  2. /*Tai sao em lai bo anh?*/
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. using int64=long long;
  6. #define ll long long
  7. const int MOD=1e9+7;
  8. const int MAX=1e6+100;
  9. typedef pair<int,int> ii;
  10. const int L=6000000;
  11. const int MAXP=400000;
  12. signed main(){
  13.     #define name "HsonW"
  14.     ios::sync_with_stdio(0);
  15.     cin.tie(NULL);
  16.     if(fopen(name ".inp", "r")){
  17.         freopen(name ".inp", "r", stdin);
  18.         freopen(name ".out", "w", stdout);
  19.     }
  20.     vector<bool>p(L+1,1);
  21.     p[0]=p[1]=0;
  22.     for(int i=2;i*i<=L;i++){
  23.         if(p[i]){
  24.             for(int j=i*i;j<=L;j+=i){
  25.                 p[j]=0;
  26.             }
  27.         }
  28.     }
  29.     vector<int>pr;
  30.     pr.reserve(MAXP);
  31.     for(int i=2;i<=L&&pr.size()<MAXP;i++){
  32.         if(p[i]) pr.push_back(i);
  33.     }
  34.  
  35.     int np=pr.size();
  36.     vector<ll>P(np+1,0);
  37.     for(int i=1;i<=np;i++){
  38.         P[i]=P[i-1]+pr[i-1];
  39.     }
  40.  
  41.     int T;
  42.     cin>>T;
  43.     while(T--){
  44.         int n;
  45.         cin>>n;
  46.  
  47.         vector<ll>a(n);
  48.         for(int i=0;i<n;i++) cin>>a[i];
  49.         sort(a.begin(),a.end(),greater<ll>());
  50.         vector<ll>S(n+1,0);
  51.         for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i-1];
  52.         int k=0;
  53.         for(int i=1;i<=n&&i<=np;i++){
  54.             if(S[i]>=P[i]) k=i;
  55.             else break;
  56.         }
  57.         cout<<(n-k)<<"\n";
  58.     }
  59. }
Success #stdin #stdout 0.06s 8512KB
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/jnOMv8
language:
C++14 (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!