fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1 << (n))
  6. #define TASK "TASK"
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8.  
  9. #define fi first
  10. #define se second
  11. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  12. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  13.  
  14. #define mii map<int,int>
  15. #define umi unordered_map<int, int>
  16. #define pii pair<int,int>
  17. #define vi vector<int>
  18.  
  19. using namespace std;
  20.  
  21. const int oo = 1e18;
  22. const int mod = 1e9 + 7;
  23. const int nmax = 1e6 + 8;
  24. const int base = 31;
  25.  
  26. int n, res, a[nmax], pf[nmax], k;
  27.  
  28. int calc(int l, int r){
  29.     if(l > r) return 0;
  30.     return pf[r] - pf[l - 1];
  31. }
  32.  
  33. bool check(int val){
  34.     int s = 0;
  35.     if(pf[n] - val <= k) {
  36. //        cout << pf[n] << ' ' << val << endl;
  37.         return true;
  38.     }
  39.     for(int i = n; i >= n - val + 1; --i){
  40.         int j = n - i + 1;
  41.         int tmp = val - j;
  42.         int cur = max(0LL, a[1] - tmp);
  43.         if(cur * (j + 1) + calc(2, i - 1) <= k){
  44. //            cout << j << ' ' << val << ' ' << cur * (j + 1) + calc(2, i - 1) << endl;
  45.             return 1;
  46.         }
  47.     }
  48.     return false;
  49. }
  50.  
  51. main(){
  52.     fast;
  53.     openfile();
  54.     cin >> n >> k;
  55.     for(int i = 1; i <= n; ++i) {
  56.         cin >> a[i];
  57.     }
  58.     sort(a + 1,a + n + 1);
  59.     for(int i = 1; i <= n; ++i) {
  60.         pf[i] = pf[i - 1] + a[i];
  61.     }
  62.     int l = 0, r = a[1] + n;
  63.     while(l <= r){
  64.         int mid = (l + r) >> 1;
  65.         if(check(mid)){
  66.             r = mid - 1;
  67.         }
  68.         else l = mid + 1;
  69.     }
  70.     cout << l;
  71. }
  72.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xsPXGb
9 11
8 10 3 4 7 2 10 4 6
language:
C++14 (gcc 8.3)
created:
3 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!