fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define el "\n"
  4. #define vc vector
  5. #define st string
  6. #define un unsigned
  7. #define ll long long
  8. #define mod(n) ((n%mod)+mod)%mod
  9. #define all(d) d.begin(), d.end()
  10. #define rt(x) return void(cout<<x)
  11. #define sums(n) (((un ll)n*(n+1))/2)
  12. #define findd(s,v) (s.find(v)!=s.end())
  13. #define mem(a,v) memset(a, v, sizeof(a))
  14. #define u64 __int128
  15. #define pl pair<ll,ll>
  16. #define sum1 prefix[idx][i]
  17. #define Mod 999999999999999989
  18.  
  19. void El_Psy_Congroo()
  20. {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL); cout.tie(NULL);
  23.    // freopen("grendizer.in", "r", stdin);
  24.     //freopen("test1.txt", "w", stdout);
  25.  
  26. }
  27. ll freq[1000002],sum[1000002],MaxNum=0;
  28. ll NeededOperations(int x)
  29. {
  30.     ll ans=freq[x]*x-sum[x];
  31.     for(ll last=x,cur=2*x;cur<=MaxNum;cur+=x,last+=x)
  32.     {
  33.         ll freq2=freq[cur]-freq[last];
  34.         ll sum2=sum[cur]-sum[last];
  35.         ans+=cur*freq2-sum2;
  36.     }
  37.     return ans;
  38. }
  39. int32_t main()
  40. {
  41.     ll n,k,Sum=0;
  42.    cin>>n>>k;
  43.     vc<int>v(n);
  44.     for(auto &i:v)
  45.     {
  46.         cin>>i;
  47.  
  48.         freq[i]++;
  49.         sum[i]+=i;
  50.         Sum+=i;
  51.         if(i>MaxNum)
  52.             MaxNum=i;
  53.     }
  54.     for(int i=1;i<=MaxNum;i++)
  55.     {
  56.         freq[i]+=freq[i-1];
  57.         sum[i]+=sum[i-1];
  58.     }
  59.     ll ma=1;
  60.     for(int i=1;i<=MaxNum;i++)
  61.     {
  62.         if(NeededOperations(i)<=k)
  63.             ma=i;
  64.     }
  65.     ll w=((k+Sum)/n >=MaxNum)? (k+Sum)/n:0;
  66.  
  67.     ma=max(ma,w);
  68.     cout<<ma;
  69. }
  70.  
  71.  
Success #stdin #stdout 0.01s 5564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
70366563570532
https://ideone.com/nHyhZZ
language:
C++ (gcc 8.3)
created:
141 days ago
visibility:
secret

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!