fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int compare(const void *a, const void *b) {
  5.     return (*(int*)a - *(int*)b);
  6. }
  7.  
  8. int min(int a, int b) {
  9.     return a < b ? a : b;
  10. }
  11.  
  12. int main() {
  13.     int n;
  14.     scanf("%d", &n);
  15.     int x[105];
  16.     for (int i = 0; i < n; i++) {
  17.         scanf("%d", &x[i]);
  18.     }
  19.  
  20.     qsort(x, n, sizeof(int), compare);
  21.  
  22.     int dp[105];
  23.     dp[0] = 0;
  24.     dp[1] = 0;
  25.  
  26.     for (int i = 2; i <= n; i++) {
  27.         dp[i] = dp[i-2] + (x[i-1] - x[i-2]);
  28.         if (i >= 3) {
  29.             dp[i] = min(dp[i], dp[i-3] + (x[i-1] - x[i-2]));
  30.         }
  31.     }
  32.  
  33.     printf("%d\n", dp[n]);
  34.     return 0;
  35. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
5
stdout 
314404997
https://ideone.com/V1RVmo
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!