Poj Solution 3042

http://poj.org/problem?id=3042

#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;

int x[1001];
__int64 ans[1001][1001][2];

int main() {
    int i, j, n, k;
    scanf( "%d%d", &n, &k );
    
    for( i=0; i<n; i++ ) {
        scanf( "%d", &x[i] );
    }

    x[n] = k;

    std::sort( x, x+n+1 );
    for( i=0; i<=n; i++ )
        if( x[i] == k ) {
            k = i;
            break;
        }

    memset( ans, 0x7f, sizeof ans );
    ans[k][k][0] = ans[k][k][1] = 0;

    for( i=k; i>=0; i-- )
    for( j=k; j<=n; j++ ) {
        if( i ) {
            if( ans[i-1][j][0] > ans[i][j][0] + (x[i]-x[i-1])*(i+n-j) )
                ans[i-1][j][0] = ans[i][j][0] + (x[i]-x[i-1])*(i+n-j);
            if(ans[i-1][j][0] > ans[i][j][1] + (x[j]-x[i-1])*(i+n-j) )
                ans[i-1][j][0] = ans[i][j][1] + (x[j]-x[i-1])*(i+n-j);
        }
        if( j < n ) {
            if( ans[i][j+1][1] > ans[i][j][0] + (x[j+1]-x[i])*(i+n-j) )
                ans[i][j+1][1] = ans[i][j][0] + (x[j+1]-x[i])*(i+n-j);
            if( ans[i][j+1][1] > ans[i][j][1] + (x[j+1]-x[j])*(i+n-j) )
                ans[i][j+1][1] = ans[i][j][1] + (x[j+1]-x[j])*(i+n-j);
        }
    }

    k = ans[0][n][0];
    if( k > ans[0][n][1] )
        k = ans[0][n][1];
    printf( "%dn", k );

    return 0;
}