fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long dp[3002][3002] ;
  5. int N , K ;
  6. const long long INF = 1e18 + 100 ;
  7. long long A[3003] ;
  8. long long solve(int pos,int present){
  9.     if(pos == N + 1){
  10.         if(present == K)
  11.             return 0 ;
  12.         return INF ;
  13.     }
  14.     long long &ret = dp[pos][present] ;
  15.     if(ret != -1)
  16.         return ret ;
  17.     long long sizeA = present ; // current sizeof set A
  18.     long long sizeB = pos - 1 - sizeA ; // current sizeof set B
  19.     // put in set B
  20.     ret = A[pos]*present - (K - sizeA)*A[pos] + solve(pos + 1,present) ;
  21.     // put in set A
  22.     if(present < K)
  23.         ret = min(ret , sizeB*A[pos] - (N - K - sizeB)*A[pos] + solve(pos + 1,present + 1)) ;
  24.     return ret ;
  25. }
  26.  
  27. int main(int argc,char* argv[]) { 
  28.     #ifndef ONLINE_JUDGE
  29.         freopen("inp.txt", "r", stdin) ;
  30.         // freopen("out.txt", "w", stdout);
  31.     #endif
  32.     cin >> N >> K ;
  33.     for(int i = 1 ; i <= N ; i++)
  34.         cin >> A[i] ;
  35.     sort(A + 1 , A + N + 1) ;
  36.     memset(dp , -1  , sizeof(dp)) ;
  37.     cout << solve(1 , 0) << endl  ;
  38.     return 0 ;
  39. }
  40.  
Success #stdin #stdout 0.03s 73920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Ge9wQ8
language:
C++14 (gcc 8.3)
created:
7 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!