Raslboyy

1620

Nov 12th, 2019
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. //#include <chrono>
  3. //#include <fstream>
  4. //#include <bits/stdc++.h>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <climits>
  8.  
  9. #define mp make_pair
  10. #define pb push_back
  11. #define eb emplace_back
  12. #define f first
  13. #define s second
  14. #define sz(x) (int)x.size()
  15. #define all(x) begin(x), end(x)
  16. #define rall(x) rbegin(x), rend(x)
  17.  
  18. using namespace std;
  19.  
  20. typedef unsigned long long ull;
  21. typedef long long ll;
  22. typedef long double ld;
  23. typedef pair<int, int> pi;
  24. typedef pair<ll, ll> pl;
  25.  
  26. int n, n_team, team_size;
  27. vector<int> vec;
  28.  
  29. bool check(int a) {
  30.     int st = 0, fn = 0;
  31.     int count = 0;
  32.     while (fn < n) {
  33.         if (fn - st + 1 >= team_size) {
  34.             count++;
  35.             st = fn = fn + 1;
  36.             continue;
  37.         }
  38.         if (vec[fn + 1] - vec[st] <= a) {
  39.             fn++;
  40.         }
  41.         else
  42.             st++;
  43.     }
  44.     return count >= n_team;
  45. }
  46.  
  47. int main() {
  48.     /*ifstream cin("in.txt");
  49.     ofstream cout("out.txt");
  50.     auto start_time = chrono::high_resolution_clock::now();*/
  51.  
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55.  
  56.    
  57.     cin >> n >> n_team >> team_size;
  58.     vec.assign(n, 0);
  59.     for (int i = 0; i < n; i++) cin >> vec[i];
  60.     sort(all(vec));
  61.     vec.push_back(INT_MAX);
  62.     int l = -1, r = vec[n - 1] - vec[0] + 1;
  63.     while (l + 1 < r) {
  64.         int mid = (l + r) / 2;
  65.         if (check(mid))
  66.             r = mid;
  67.         else
  68.             l = mid;
  69.     }
  70.     cout << r << endl;
  71.    
  72.     /*auto end_time = chrono::high_resolution_clock::now();
  73.     chrono::duration<double> duration = end_time - start_time;
  74.     cout << duration.count() << "\n";
  75.     cin.close();
  76.     cout.close();*/
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment