COCI '16 Contest 4 #3 Kas

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<int> v(n);
    11    int mx = 0;
    12    for (int i = 0; i < n; i++) {
    13        cin >> v[i];
    14        mx += v[i];
    15    }
    16    vector<vector<int>> dp(n + 1, vector<int>(mx + 1, -inf));
    17    dp[0][0] = 0;
    18    for (int i = 1; i <= n; i++) {
    19        for (int j = 0; j <= mx; j++) {
    20            dp[i][j] = dp[i - 1][j];
    21            if (dp[i - 1][abs(j - v[i - 1])] != -inf) {
    22                dp[i][j] = max(dp[i][j], dp[i - 1][abs(j - v[i - 1])] + v[i - 1]);
    23            }
    24            if (j + v[i - 1] <= mx && dp[i - 1][j + v[i - 1]] != inf) {
    25                dp[i][j] = max(dp[i][j], dp[i - 1][j + v[i - 1]] + v[i - 1]);
    26            }
    27        }
    28    }
    29    int ans = dp[n][0] / 2 + mx - dp[n][0];
    30    cout << ans << '\n';
    31    return 0;
    32}