fork 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),0LL)
  22. #define		mem0(v)			 memset(v,0,sizeof(v))
  23. #define		mem1(v)			 memset(v,-1,sizeof(v))
  24.  
  25. #define     make_unique(v)   v.erase(unique(all(v)),v.end())
  26. #define     n_p(v)           next_permutation(all(v))
  27. #define     p_p(v)           prev_permutation(all(v))
  28.  
  29.  
  30. #define     for_each(it, X)  for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
  31.  
  32. #define     printv(a)        rep( i, 0, sz(a) )    cout<<a[i]<<" ";     cout<<endl;
  33.  
  34. #define		prints(a)		 for_each(it, a)  cout<<*it<<" ";   cout<<endl;
  35.  
  36. #define		printvll(a)		 rep(i,0,sz(a))  cout<<a[i].ff<<" "<<a[i].ss<<endl; 
  37.  
  38. #define     re               return
  39.  
  40. using namespace std;
  41.  
  42. typedef     long long              ll;
  43. typedef     unsigned long long     ull;
  44. typedef     pair < int, int >      pii;
  45. typedef     pair < ll, ll >        pll;
  46. typedef     vector < pii >         vii;
  47. typedef     vector < pll >         vll;
  48. typedef     vector < int >         vi;
  49. typedef     vector < ll >          vl;
  50. typedef     vector < vl >          vvl;
  51. typedef     vector < string >      vs;
  52. typedef     vector < vs >          vvs;
  53. typedef     set< ll >              sl;
  54. typedef     set< string >          ss;
  55. typedef     set< pll >             sll;
  56. typedef     multiset< ll >         msl;
  57. typedef     map< ll, ll >          ml;
  58.  
  59.  
  60. ll gcd ( ll , ll );
  61.  
  62. ll lcm ( ll  , ll );
  63.  
  64. bool isPrime( ll );
  65.  
  66. ll power( ll , ll );
  67.  
  68. ll fact( ll );
  69.  
  70. void sieve_of_eratosthenes (  ll , vl &  );
  71.  
  72. ll roof(ll , ll);
  73.  
  74. bool isPalindrome( string );
  75.  
  76. //---------------------------------------------------------------------------------------------------------------------------------------------
  77. //---------------------------------------------------------------------------------------------------------------------------------------------
  78. const ll 	  INF  =  1e18;
  79. const ll      MOD  =  1e9 + 7;
  80. const ll      MOO  =  998244353;
  81. const double  pi   =  3.14159265358979323846;
  82.  
  83. ll n,i,v[100005],c;
  84.  
  85. bool check(int d)
  86. {
  87. 	ll h=1, p=v[0];
  88.  
  89. 	rep(i,1,n) {
  90. 		if(v[i]-p>=d) {
  91. 			h++;
  92. 			p=v[i];
  93. 		}
  94. 	}
  95.  
  96. 	if(h>=c) {
  97. 		re 1;
  98. 	}
  99. 	re 0;
  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. 	ll ans;
  115.  
  116. 	while(l<=r) {
  117. 		ll mid=l+(r-l)/2;
  118.  
  119. 		if(check(mid)==1) {
  120. 			l=mid+1;
  121. 			ans=mid;
  122. 		}
  123.  
  124. 		else {
  125. 			r=mid-1;
  126. 		}
  127. 	}
  128.  
  129. 	cout<<ans<<endl;
  130.  
  131.  
  132. }
  133.  
  134.  
  135. int main()
  136. {
  137.     boost;
  138.     ll t=1;
  139. 	cin>>t;
  140.  
  141. 	rep(i,0,t)
  142.     {
  143.    		// cout<<"Case #"<<i+1<<": ";
  144.     	solve();
  145. 	   	// cout<<endl;
  146.     }
  147.  
  148. }
  149.  
  150. //---------------------------------------------------------------------------------------------------------------------------------------------
  151. //---------------------------------------------------------------------------------------------------------------------------------------------
  152.  
  153. // HCF
  154.  
  155. ll gcd ( ll a , ll b )  {
  156.  
  157. 	return __gcd ( a , b ) ;
  158.  
  159. 	/*
  160.  
  161. 	if ( a==0 )
  162. 	return b ;
  163.  
  164. 	return gcd ( b%a , a ) ;	
  165.  
  166. 	*/
  167. }
  168.  
  169. // LCM
  170.  
  171. ll lcm ( ll a , ll b )  {
  172.  
  173. 	return ( a * b ) / ( __gcd ( a , b ) ) ;
  174.  
  175. }
  176.  
  177. // PRIME 
  178.  
  179. bool isPrime( ll n )
  180. {
  181.     for( ll i=2 ; i*i<=n ; i++) 
  182. 	{
  183.         if( n % i == 0)
  184.         return false;
  185.     }
  186.  
  187.     return true;
  188. }
  189.  
  190. // POWER
  191.  
  192. ll power( ll a , ll b) {
  193. 		/*if (b == 0) return 1;
  194.         if (b == 1) return a;
  195.         if (b%2 == 1) return (a*power(a,b-1))%MOD;
  196.         ll x = power(a,b/2)%MOD;
  197.         return (x*x)%MOD;*/
  198.  
  199. 	ll c=MOD;
  200. 	ll ans=1;
  201.  
  202. 	while(b) {
  203. 		if(b%2) {
  204. 			ans=(ans*(a%c))%c;
  205. 			// ans*=a;
  206. 		}
  207.  
  208. 		a=((a%c)*(a%c))%c;
  209. 		// a=a*a;
  210. 		b>>=1;
  211. 	}
  212.  
  213. 	return ans;
  214. }
  215.  
  216. // FACTORIAL
  217.  
  218. ll fact(ll n) {
  219. 	ll m=INF;
  220.  
  221. 	ll h = 1;
  222.  
  223. 	rep(i,1,n+1) {
  224. 		h=(h*i);
  225. 	}
  226.  
  227. 	return h;	
  228.  
  229. }
  230.  
  231. // SIEVE of ERATOSTHENES
  232.  
  233. void sieve_of_eratosthenes (ll n, vl &a) {
  234.  
  235. 	a[0]=a[1]=0;
  236.  
  237. 	for(ll i=2; i*i<=10000007 ; i++) {
  238. 		if(a[i]) {
  239. 			for(ll j=i+i; j<=10000007 ; j+=i) {
  240. 				a[j]=0;
  241. 			}
  242. 		}
  243. 	}
  244.  
  245. }
  246.  
  247. // CEILING FUNCTION
  248.  
  249. ll roof(ll a, ll b) {
  250.  
  251. 	return (a + b - 1) / (b) ;
  252.  
  253. } 
  254.  
  255. // PALINDROME
  256.  
  257. bool isPalindrome(string s) {
  258. 	rep(i,0,sz(s)/2) {
  259. 		if(s[i]!=s[sz(s)-i-1]) re 0;
  260. 	}
  261.  
  262. 	re 1;
  263. }
  264.  
  265.  
Success #stdin #stdout 0s 5612KB
comments (?)
stdin
copy 
1
2 2 
1
3
stdout
copy 
2
https://ideone.com/8oEVbg
problem AGGRCOW, based on SPOJ submission 27980931 (CPP14), 2021-05-30 07:32:37
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!