fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define ld long double
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define nn '\n'
  12. #define pi pair<int, int>
  13. #define unmp unordered_map
  14. #define uns unordered_set
  15. #define lb lower_bound
  16. #define ub upper_bound
  17. #define pq priority_queue
  18. #define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  19. #define TASK "fishing"
  20.  
  21.  
  22. const int INF = 1e15;
  23. int mod = 1e9+7;
  24. const int N = 1e4 + 5;
  25. int MOD = 998244353;
  26. int bit[200000];
  27. int n, k;
  28. int a[N];
  29. int kq = INF;
  30. int mx = 0;
  31. bool anhphucbell(int mid){
  32.     int hehe = a[1];
  33.     int dem = 1;
  34.     for(int i = 2; i <= n ;i++){
  35.         if(a[i] - hehe >= mid){
  36.             dem++;
  37.             hehe = a[i];
  38.         }
  39.     }
  40.     return dem >= k;
  41. }
  42. signed main(){
  43.     ios_base::sync_with_stdio(0);
  44. 	cin.tie(0);
  45. 	cout.tie(0);
  46.     if(fopen(TASK".INP","r")){
  47.         freopen(TASK".INP","r",stdin);
  48.         freopen(TASK".OUT","w",stdout);
  49.     }
  50.     cin >> n >> k;
  51.     for(int i = 1; i <= n; i++ ){
  52.         cin >> a[i];
  53.     }
  54.     int l = 1, r = 1e9, kq = -1;
  55.     while(l <= r){
  56.         int mid = (l + r) / 2;
  57.         if(anhphucbell(mid)){
  58.             kq = mid;
  59.             l = mid + 1;
  60.         }
  61.         else{
  62.             r = mid - 1;
  63.         }
  64.  
  65.     }
  66.     cout << kq << nn;
  67. 	return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6 3
2 5 7 11 15 20
stdout
copy 
9
https://ideone.com/8GcFTZ
language:
C++14 (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!