fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define nmax 1000007
  5. #define nhanh ios_base::sync_with_stdio(0);cin.tie(NULL),cout.tie(NULL);
  6. #define pll pair<ll,ll>
  7. #define fi first
  8. #define se second
  9. const ll mod = 1e9 + 7;
  10. ll n,k,x,y,a[nmax],dp[2007][2007][3];
  11. int main()
  12. {
  13.    cin >> n >> k;
  14.  
  15.    for (int i = 1; i <= n; i++)
  16.    {
  17.        cin >> a[i];
  18.    }
  19.    sort (a + 1, a + 1 + n, greater<ll>());
  20.    memset(dp,0x3f,sizeof(dp));
  21.    dp[0][0][0] = 0;
  22.    dp[0][0][1] = 0;
  23.  
  24.      for (int j = 1; j <= k; j++)
  25.    for (int i = 1; i <= n; i++)
  26.    {
  27.        dp[i][j][0] =  min(dp[i - 1][j][0], dp[i - 1][j][1] - a[i]);
  28.        dp[i][j][1] =  min(dp[i - 1][j][1], dp[i - 1][j - 1][0] + a[i]);
  29.    }
  30.  
  31.    cout <<dp[n][k][0];
  32. }
  33.  
  34.  
  35.  
Success #stdin #stdout 0.02s 98948KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sJeIbI
language:
C++14 (gcc 8.3)
created:
4 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!