fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define     boost            ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
  4. #define     pb               push_back	
  5. #define     pf               push_front
  6. #define     pob              pop_back
  7. #define     pof              pop_front	
  8. #define     mp              make_pair
  9. #define     ff               first
  10. #define     ss               second
  11. #define     IN               insert
  12. #define     endl             "\n"
  13.  
  14. #define     rep(i,a,b)       for(ll i=a; i<b; i++)
  15. #define     rev(i,a,b)       for(ll i=a; i>=b; i--)
  16.  
  17. #define     decimal(n)       fixed << setprecision(n) 
  18. #define     all(v)           v.begin(), v.end() 
  19. #define     rall(v)          v.rbegin(), v.rend()
  20. #define     sz(v)            v.size()
  21. #define     total_sum(v)     accumulate(all(v),0)  
  22.  
  23. #define     make_unique(v)   v.erase(unique(all(v)),v.end())
  24. #define     n_p(v)           next_permutation(all(v))
  25. #define     p_p(v)           prev_permutation(all(v))
  26.  
  27.  
  28. #define     for_each(it, X)  for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
  29.  
  30. #define     printv(a)        rep( i, 0, sz(a) )    cout<<a[i]<<" ";     cout<<endl;
  31.  
  32. #define		prints(a)		 for_each(it, a)  cout<<*it<<" ";   cout<<endl;
  33.  
  34. #define		printvll(a)		 rep(i,0,sz(a))  cout<<a[i].ff<<" "<<a[i].ss<<endl; 
  35.  
  36. #define     re               return
  37.  
  38. using namespace std;
  39.  
  40. typedef     long long              ll;
  41. typedef     unsigned long long     ull;
  42. typedef     pair < int, int >      pii;
  43. typedef     pair < ll, ll >        pll;
  44. typedef     vector < pii >         vii;
  45. typedef     vector < pll >         vll;
  46. typedef     vector < int >         vi;
  47. typedef     vector < ll >          vl;
  48. typedef     vector < vl >          vvl;
  49. typedef     vector < string >      vs;
  50. typedef     vector < vs >          vvs;
  51. typedef     set< ll >              sl;
  52. typedef     set< string >          ss;
  53. typedef     set< pll >             sll;
  54. typedef     multiset< ll >         msl;
  55. typedef     map< ll, ll >          ml;
  56.  
  57.  
  58. ll gcd ( ll , ll );
  59.  
  60. ll lcm ( ll  , ll );
  61.  
  62. bool isPrime( ll );
  63.  
  64. ll power( ll , ll );
  65.  
  66. ll fact( ll );
  67.  
  68. void sieve_of_eratosthenes (  ll , vl &  );
  69.  
  70. ll roof(ll , ll);
  71.  
  72. bool isPalindrome( string );
  73.  
  74. //---------------------------------------------------------------------------------------------------------------------------------------------
  75. //---------------------------------------------------------------------------------------------------------------------------------------------
  76. const ll 	  INF  =  1e18;
  77. const ll      MOD  =  1e9 + 7;
  78. const ll      MOO  =  998244353;
  79. const double  pi   =  3.14159265358979323846;
  80. const ll      MAX  =  100010;
  81.  
  82. ll n,i,v[100005],c;
  83.  
  84. bool check(int d)
  85. {
  86. 	ll h=1, p=v[0];
  87.  
  88. 	rep(i,1,n) {
  89. 		if(v[i]-p>=d) {
  90. 			h++;
  91. 			p=v[i];
  92. 		}
  93. 	}
  94.  
  95. 	if(h>=c) {
  96. 		re 1;
  97. 	}
  98. 	re 0;
  99.  
  100.  
  101. }
  102.  
  103.  
  104. void solve()
  105. {
  106. 	cin>>n>>c;
  107.  
  108. 	rep(i,0,n) {
  109. 		cin>>v[i];
  110. 	}
  111. 	sort(v,v+n);
  112.  
  113. 	ll l=0, r=v[n-1]-v[0];
  114.  
  115. 	while(l+1<r) {
  116. 		ll mid=l+(r-l)/2;
  117.  
  118. 		if(check(mid)) {
  119. 			l=mid;
  120. 		}
  121.  
  122. 		else {
  123. 			r=mid;
  124. 		}
  125. 	}
  126.  
  127. 	cout<<l<<endl;
  128.  
  129. }
  130.  
  131.  
  132. int main()
  133. {
  134.     boost;
  135.     ll t=1;
  136. 	cin>>t;
  137.  
  138. 	rep(i,0,t)
  139.     {
  140.    		// cout<<"Case #"<<i+1<<": ";
  141.     	solve();
  142. 	   	// cout<<endl;
  143.     }
  144.  
  145. }
  146.  
  147. //---------------------------------------------------------------------------------------------------------------------------------------------
  148. //---------------------------------------------------------------------------------------------------------------------------------------------
  149.  
  150. // HCF
  151.  
  152. ll gcd ( ll a , ll b )  {
  153.  
  154. 	return __gcd ( a , b ) ;
  155.  
  156. 	/*
  157.  
  158. 	if ( a==0 )
  159. 	return b ;
  160.  
  161. 	return gcd ( b%a , a ) ;	
  162.  
  163. 	*/
  164. }
  165.  
  166. // LCM
  167.  
  168. ll lcm ( ll a , ll b )  {
  169.  
  170. 	return ( a * b ) / ( __gcd ( a , b ) ) ;
  171.  
  172. }
  173.  
  174. // PRIME 
  175.  
  176. bool isPrime( ll n )
  177. {
  178.     for( ll i=2 ; i*i<=n ; i++) 
  179. 	{
  180.         if( n % i == 0)
  181.         return false;
  182.     }
  183.  
  184.     return true;
  185. }
  186.  
  187. // POWER
  188.  
  189. ll power( ll a , ll b) {
  190. 	ll c=INF;
  191. 	ll ans=1;
  192.  
  193. 	while(b) {
  194. 		if(b%2) {
  195. 			ans=ans*a;
  196. 		}
  197.  
  198. 		a=a*a;
  199. 		b>>=1;
  200. 	}
  201.  
  202. 	return ans;
  203. }
  204.  
  205. // FACTORIAL
  206.  
  207. ll fact(ll n) {
  208. 	ll m=INF;
  209.  
  210. 	ll h = 1;
  211.  
  212. 	rep(i,1,n+1) {
  213. 		h=(h*i);
  214. 	}
  215.  
  216. 	return h;	
  217.  
  218. }
  219.  
  220. // SIEVE of ERATOSTHENES
  221.  
  222. void sieve_of_eratosthenes (ll n, vl &a) {
  223.  
  224. 	a[0]=a[1]=0;
  225.  
  226. 	for(ll i=2; i*i<=10000007 ; i++) {
  227. 		if(a[i]) {
  228. 			for(ll j=i+i; j<=10000007 ; j+=i) {
  229. 				a[j]=0;
  230. 			}
  231. 		}
  232. 	}
  233.  
  234. }
  235.  
  236. // CEILING FUNCTION
  237.  
  238. ll roof(ll a, ll b) {
  239.  
  240. 	return (a + b - 1) / (b) ;
  241.  
  242. } 
  243.  
  244. // PALINDROME
  245.  
  246. bool isPalindrome(string s) {
  247. 	rep(i,0,sz(s)/2) {
  248. 		if(s[i]!=s[sz(s)-i-1]) re 0;
  249. 	}
  250.  
  251. 	re 1;
  252. }
  253.  
  254.  
Success #stdin #stdout 0.01s 5504KB
comments (?)
stdin
copy 
1
2 2 
1
3
stdout
copy 
1
https://ideone.com/lekcZ4
problem AGGRCOW, based on SPOJ submission 27931370 (CPP14), 2021-05-21 19:37:56
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!