fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const int MAXN = 1e5 + 5;
  5. ll a[MAXN], st[MAXN * 4], res = 1e18;
  6. int n, k;
  7. void build (int id, int l, int r)
  8. {
  9.     if (l == r)
  10.     {
  11.         st[id]= a[l];
  12.         return;
  13.     }
  14.     int mid = (l + r) / 2;
  15.     build(id * 2, l, mid);
  16.     build(id * 2 + 1, mid + 1, r);
  17.     st[id] = max(st[id * 2], st[id * 2 + 1]);
  18. }
  19. ll get (int id, int l, int r, int u, int v)
  20. {
  21.     if (l > v || u > r)
  22.         return -1e18;
  23.     if (l >= u && v >= r)
  24.         return st[id];
  25.     int mid = (l + r) / 2;
  26.     return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
  27. }
  28. void solve1()
  29. {
  30.     for (int i = 1;i < n; i++)
  31.         a[i] = a[i+1] - a[i];
  32.     n--;
  33.     build(1, 1, n);
  34.     for (int i = 1;i <= n - k; i++)
  35.         res = min(get(1, 1, n, i, n - k + i - 1), res);
  36.     cout << res;
  37. }
  38. void solve2 ()
  39. {
  40.     for (int i = 1; i <= n - k; i++)
  41.     {
  42.         ll diff = -1e18;
  43.         for (int j = i; j < n - k + i - 1; j++)
  44.             diff = max(a[j+1] - a[j], diff);
  45.         res = min(res, diff);
  46.     }
  47.     cout << res;
  48. }
  49. int main ()
  50. {
  51.     cin >> n >> k;
  52.     for (int i = 1;i <= n; i++)
  53.         cin >> a[i];
  54.     sort(a + 1, a + n + 1);
  55.     if (n <= 2e3)
  56.         solve2();
  57.     else
  58.         solve1();
  59. }
  60.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/1xUdGk
language:
C++ (gcc 8.3)
created:
43 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!