fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "dovuive"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=1e5+5;
  19. int n,k;
  20. ll a[MAX],ans;
  21. vector<pair<ll,ll>> v;
  22.  
  23. int main()
  24. {
  25.     fastio
  26.     freopen(FILE ".inp","r",stdin);
  27.     freopen(FILE ".out","w",stdout);
  28.  
  29.     cin>>n>>k;
  30.     map<ll,ll> mp;
  31.     foru(i,1,n)
  32.     {
  33.         cin>>a[i];
  34.         mp[a[i]]++;
  35.     }
  36.     v.pb(make_pair(0LL,0LL));
  37.     for(pair<ll,ll> p:mp) 
  38.     {
  39.         v.pb(p); 
  40.     }
  41.     ford(i,v.size()-1,1)
  42.     {
  43.         // cerr<<v[i].fi<<' '<<v[i].se<<el;
  44.         ll dist=v[i].fi-v[i-1].fi;
  45.         if(k>dist*v[i].se)
  46.         {
  47.             k-=dist*v[i].se;
  48.             ans+=((v[i].fi+v[i-1].fi+1)*dist/2)*v[i].se;
  49.             v[i-1].se+=v[i].se;
  50.         }
  51.         else 
  52.         {
  53.             ll tmp=k/v[i].se,du=k%v[i].se;
  54.             // cerr<<tmp<<' '<<du<<el;
  55.             ans+=(v[i].fi+v[i].fi-tmp+1)*(tmp)/2*v[i].se+((v[i].fi-tmp)*du);
  56.             cout<<ans;
  57.             return 0;
  58.         }
  59.         // cerr<<k<<el;
  60.         // cerr<<ans<<el;
  61.     }
  62.     cout<<ans;
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ktMKWM
language:
C++14 (gcc 8.3)
created:
11 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!