mayoko’s diary

プロコンとかいろいろ。

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;
}