fork download
copy 
  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. #define rep(i, n) for(int i = 0; i < n; i++)
  10.  
  11. ll d[1111];
  12. ll t[1111][1111];
  13. ll dp[1111][1111];
  14.  
  15. int mind(ll* pre, int b, int l, int g) {
  16.   ll mm = (ll)1 << 60;
  17.   int mb = -1;
  18.   for(int i = b; i <= l; i++) {
  19.     if(mm > pre[i] + t[i][g]) {
  20.       mm = pre[i] + t[i][g];
  21.       mb = i;
  22.     }
  23.   }
  24.   return mb;
  25. }
  26.  
  27. void step_dfs(int b, int l, int mb, int ml, ll* pre, ll* nex) {
  28.   if(b > l) {return;}
  29.   int m = (b + l) / 2;
  30.   int w = mind(pre, mb, ml, m);
  31.   assert(w != -1);
  32.   nex[m] = pre[w] + t[w][m];
  33.   step_dfs(b, m - 1, mb, w, pre, nex);
  34.   step_dfs(m + 1, l, w, ml, pre, nex);
  35. }
  36.  
  37. void step(ll* pre, ll* nex, int n) {
  38.   step_dfs(0, n, 0, n, pre, nex);
  39. }
  40.  
  41. int main() {
  42.   int n, m;
  43.   scanf("%d%d", &n, &m);
  44.   if(m > n) {
  45.     m = n;
  46.   }
  47.   rep(i, n) {
  48.     scanf("%lld", d + i);
  49.   }
  50.   sort(d, d + n);
  51.   rep(i, n) {
  52.     rep(j, n) {
  53.       t[i][j] = 0;
  54.     }
  55.   }
  56.   rep(k, n * 2 - 1) {
  57.     int a = k / 2;
  58.     if(k % 2 == 0) {
  59.       t[a][a + 1] = 0;
  60.       for(int i = 1; a - i >= 0 && a + 1 + i <= n; i++) {
  61.         t[a - i][a + 1 + i] = t[a - (i - 1)][a + 1 + (i - 1)] + d[a + i] - d[a - i];
  62.       }
  63.     }
  64.     else {
  65.       t[a][a + 2] = d[a + 1] - d[a];
  66.       for(int i = 1; a - i >= 0 && a + 2 + i <= n; i++) {
  67.         t[a - i][a + 2 + i] = t[a - (i - 1)][a + 2 + (i - 1)] + d[a + 1 + i] - d[a - i];
  68.       }
  69.     }
  70.   }
  71.   dp[0][0] = 0;
  72.   rep(i, n) {
  73.     dp[0][i + 1] = (ll)1 << 60;
  74.   }
  75.   rep(i, m) {
  76.     step(dp[i], dp[i + 1], n);
  77.   }
  78.   printf("%lld\n", dp[m][n]);
  79. }
  80.  
Success #stdin #stdout 0s 22760KB
comments (?)
stdin
copy 
5 2
-3
-1
0
2
5
stdout
copy 
6
https://ideone.com/lS24bd
language:
C++14 (gcc 8.3)
created:
7 years 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!