2419번: Beetle

https://www.acmicpc.net/problem/2419

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, x[301], dp[2][301][301][301], ck[2][301][301][301];
int f(int d, int l, int r, int c) {
    if (!c) return (r - l)*m;
    if (ck[d][l][r][c]) return dp[d][l][r][c];
    ck[d][l][r][c] = 1;
    int t = 0;
    if (l) t = f(0, l - 1, r, c - 1) - (d ? x[r] - x[l - 1] : x[l] - x[l - 1])*c;
    if (r < n) t = max(t, f(1, l, r + 1, c - 1) - (d ? x[r + 1] - x[r] : x[r + 1] - x[l])*c);
    return dp[d][l][r][c] = t;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", x + i);
    sort(x, x + 1 + n);
    int s = lower_bound(x, x + 1 + n, 0) - x, res = 0;
    for (int i = 1; i <= n; i++) res = max({ res,f(0,s,s,i),f(1,s,s,i) });
    printf("%d", res);
    return 0;
}