fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  4. using namespace std;
  5.  
  6. void input(){
  7. 	#define taskname ""
  8. 	if(fopen(taskname ".inp", "r")){
  9. 		freopen(taskname ".inp", "r", stdin);
  10. 		freopen(taskname ".out","w",stdout);
  11. 	}
  12. }
  13. const int N = 2e5+1;
  14. const ll INF =1e18;
  15. const int Q =1e9+7;
  16. ll a[N];
  17. ll n,k;
  18. array<ll,2>get(ll mid){
  19.     vector<array<ll,2>>dp(n+1,{INF,0});
  20.     dp[0] = {0,0};
  21.     for(ll i=1;i<=n;++i){
  22.         if(i >=1) dp[i] = min(dp[i],dp[i-1]);
  23.         if(i >= 2) dp[i] = min(dp[i],{dp[i-2][0] + (a[i]-a[i-1])*(a[i]-a[i-1]) - mid, dp[i-2][1] - 1});
  24.     }
  25.     return dp[n];
  26. }
  27. int main(){
  28. 	cin.tie(0)->sync_with_stdio(0);
  29. 	cout.tie(0);
  30. 	input();
  31. 	cin >> n >> k;
  32.     for(ll i=1;i<=n;++i) cin >> a[i];
  33.     sort(a+1,a+n+1);
  34.     ll l = 0, r = 1e14;
  35.     ll ans = -1;
  36.     array<ll,2>res = {0,0};
  37.     while(l <= r){
  38.         ll mid = (l+r) >> 1;
  39.         auto cur = get(mid);
  40.         if(-cur[1] >= k){
  41.             ans = mid;
  42.             res = cur;
  43.             r = mid - 1;
  44.         }
  45.         else l = mid+1;
  46.     }
  47.     cout << res[0] + ans*k << endl;
  48. 	return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5 2 
2 5 3 3 6
stdout
copy 
1
https://ideone.com/nmt4id
language:
C++ (gcc 8.3)
created:
6 days 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!