fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Hoshimachi signed
  3. #define Suisei main
  4. using namespace std;
  5. #define int long long
  6. #define pii pair<int,int>
  7. const int N=2e5+5;
  8. int n,k;
  9. int a[N],b[N];
  10. pii dp[N];
  11. pii ss(pii a, pii b){
  12.     if(a.first!=b.first) return min(a,b);
  13.     return max(a,b);
  14. }
  15. Hoshimachi Suisei(){
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0); cout.tie(0);
  18.     // freopen(".inp", "r", stdin);
  19.     // freopen(".out", "w", stdout);
  20.     cin>>n>>k;
  21.     for(int i=1; i<=n; i++){
  22.         cin>>a[i];
  23.     }
  24.     sort(a+1,a+1+n);
  25.     for(int i=1; i<n; i++){
  26.         b[i]=(a[i+1]-a[i])*(a[i+1]-a[i]);
  27.     }
  28.     int lo=-1e14,hi=1e14,mid,kq=0;
  29.     int ans=0;
  30.     while(lo<=hi){
  31.         mid=(lo+hi)/2;
  32.         dp[0]={0,0};
  33.         for(int i=1; i<n; i++){
  34.             pii opt=dp[i-1];
  35.             pii nval=i==1?pii(b[1]-mid,1LL):pii(dp[i-2].first+b[i]-mid,dp[i-2].second+1);
  36.             opt=ss(opt,nval);
  37.             dp[i]=opt;
  38.         }
  39.         if(dp[n-1].second>=k){
  40.             hi=mid-1;
  41.             ans=dp[n-1].first;
  42.             kq=mid;
  43.         }
  44.         else{
  45.             lo=mid+1;
  46.         }
  47.     }
  48.     cout<<ans+kq*k;
  49. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
23207910761920
https://ideone.com/byvmyW
language:
C++ (gcc 8.3)
created:
3 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!