fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.   ios_base::sync_with_stdio(false);
  6.   cin.tie(NULL);
  7.   long long t,n,c;
  8.   cin>>t;
  9.   vector<long long> ans;
  10.   while(t--){
  11.     cin>>n>>c;
  12.     long long x[n];
  13.     long long mind=LLONG_MAX;
  14.     for(long long i=0;i<n;i++){
  15.       cin>>x[i];
  16.       mind=min(x[i],mind);
  17.     }
  18.     sort(x,x+n);
  19.  
  20.     long long low=mind;
  21.     long long high=x[n-1]-x[0];
  22.     long long mid;
  23.     long long maxd=-1;
  24.  
  25.     while(low < high){
  26.       mid = low+(high-low)/2;
  27.       long long cows=1;
  28.       long long idx=0;
  29.       for(long long i=1;i<n;i++){
  30.         if(x[i]-x[idx] >= mid) {cows++; idx=i;}
  31.       }
  32.       if(cows >= c) {low=mid+1; maxd=max(maxd,mid);}
  33.       else high=mid;
  34.     }
  35.     ans.push_back(maxd);
  36.   }
  37.  
  38.   for(vector<long long>::iterator it=ans.begin();it!=ans.end();it++){
  39.     cout<<*it<<endl;
  40.   }
  41.   return 0;
  42. }
  43.  
Runtime error #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tI15Yh
language:
C++ (gcc 8.3)
created:
5 years 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!