Submission #36063085

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
int arr[3001];
const int INF = 987654321;
int dp[3001][3001][2];
bool vis[3001][3001][2];
int N, M;
int sol(int x, int s, int m) {
    // given arr[x..N], make s
    if (x == N) {
        return s == 0 ? 0 : INF;
    } else if (s < 0)
        return INF;
    if (vis[x][s][m]) return dp[x][s][m];
    int ret = min({INF, sol(x + 1, s - (m ? 0 : arr[x]), m),
                   1 + sol(x + 1, s - (((!m) ? 0 : arr[x])), !m)});
    vis[x][s][m] = true;
    return dp[x][s][m] = ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= M; i++) {
        int ans = sol(0, i, 0);
        cout << (ans == INF ? -1 : (ans+1)/2) << '\n';
    }
}

Submission Info

Judge Result