fork download
copy 
  1. #include <algorithm>
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define el '\n'
  5. #define oo LLONG_MAX >> 2
  6. #define all(x) x.begin(), x.end()
  7. #define allr(x) x.rbegin(), x.rend()
  8. #define pb push_back
  9. #define pep_Guardiola                                                          \
  10.   ios::sync_with_stdio(0);                                                     \
  11.   cin.tie(0);                                                                  \
  12.   cout.tie(0);
  13. using namespace std;
  14.  
  15. signed main() {
  16.   pep_Guardiola
  17.  
  18.       int n,
  19.       k;
  20.   cin >> n >> k;
  21.   vector<int> a(n);
  22.   for (auto &i : a)
  23.     cin >> i;
  24.   sort(all(a));
  25.   auto ok = [&](int x) -> bool {
  26.     int tmp = 0;
  27.     for (int i = 0; i < n; i++)
  28.       tmp += upper_bound(a.begin() + i + 1, a.end(), a[i] + x) - (a.begin() + i + 1);
  29.     return tmp < k;
  30.   };
  31.   int l = 0, r = a[n - 1] - a[0];
  32.   while (l <= r) {
  33.     int mid = (r + l) >> 1;
  34.     if (ok(mid))
  35.       l = mid + 1;
  36.     else
  37.       r = mid - 1;
  38.   }
  39.   cout << ++r << el;
  40. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3 1
4 6 1
stdout
copy 
2
https://ideone.com/SzfRXM
language:
C++ (gcc 8.3)
created:
1 day 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!