AtCoder Regular Contest 043 D - 引っ越し
SRM div1 med っぽい雰囲気。
解法
スライド通り。
www.slideshare.net
const int MAXM = 1010; const ll INF = 1ll<<60; int P[MAXM]; int sum[MAXM]; ll dp[2][MAXM*100]; // dp[n][lsum] = max int N, M; ll ans = 0; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; ll s = 0; ll ss = 0; for (int i = 0; i < M; i++) { cin >> P[i]; s += P[i]; } sort(P, P+M); reverse(P, P+M); for (int i = 0; i < 2; i++) for (int j = 0; j <= s; j++) { dp[i][j] = -INF; } dp[0][0] = 0; for (int i = 0; i < M; i++) { int cur = i%2; int tar = cur^1; for (int x = 0; x <= ss; x++) { dp[tar][x+P[i]] = max(dp[tar][x+P[i]], dp[cur][x] + (ll)x*(s-x)); ll r = ss-x; dp[tar][x] = max(dp[tar][x], dp[cur][x] + r*(s-r)); } ss += P[i]; } ll ans = 0; for (int i = 0; i <= s; i++) { ans = max(ans, dp[M%2][i]+(ll)(N-M+1)*i*(s-i)); } cout << ans << endl; return 0; }