Untitled

mail@pastecode.io avatar
unknown
plain_text
11 days ago
2.7 kB
0
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t

vector<vector<int> > dp;
int maxn = 100005;
int n;

int solve(int i, int remainingSum, vector<int> &arr) {
    if (i == n) {
        return remainingSum == 0;
    }
    if (remainingSum < 0) {
        return 0;
    }

    if (dp[i][remainingSum] != -1) {
        return dp[i][remainingSum];
    }

    int ans = solve(i + 1, remainingSum, arr);
    if (remainingSum >= arr[i]) {
        ans |= solve(i + 1, remainingSum - arr[i], arr);
    }

    return dp[i][remainingSum] = ans;
}


void findSet(int i, int remainingSum, vector<int> &st, vector<int> &arr) {
    if (i == n) {
        return;
    }

    if (remainingSum < 0) {
        return;
    }

    if (solve(i + 1, remainingSum, arr) == 1) {
        findSet(i + 1, remainingSum, st, arr);
    } else if (solve(i + 1, remainingSum - arr[i], arr) == 1){
        st.push_back(i);
        findSet(i + 1, remainingSum - arr[i], st, arr);
    }
}


vector<vector<int>> subset_queries(vector<int> &arr, vector<int> &queries) {
    
    vector<vector<int> > ans;
    n = arr.size();
    dp.assign(n + 1, vector<int> (maxn, -1));

    for (auto query: queries) {
        solve(0, query, arr);

        if (dp[0][query] == 1) {
            vector<int> st;
            findSet(0, query, st, arr);
            ans.push_back(st);
        } else {
            ans.push_back({-1});
        }
    }

    return ans;
}

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> arr(N);
    for (int i = 0; i < N; i++)cin >> arr[i];
    vector<int> queries(Q);
    for (int i = 0; i < Q; i++)cin >> queries[i];
    auto ans = subset_queries(arr, queries);

    // checker.
    if (ans.size() != Q) {
        cout << 101 << endl;
        return;
    }
    for (int i = 0; i < Q; i++) {
        auto x = ans[i];
        if (x.size() == 0) {
            cout << 101 << endl;
            continue;
        }
        if (x.size() == 1 && x[0] == -1) {
            cout << -1 << endl;
            continue;
        }
        ll sum = 0, p = -10;
        for (auto y : x) {
            if (y < 0 || y >= N || p >= y ) { // valid 0-indexed.
                sum = -1111;
                break;
            }
            p = y;
            sum += arr[y];
        }
        if (sum == queries[i]) {
            cout << 1 << endl;
        }
        else cout << 101 << endl;
    }
}
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

#ifdef Mastermind_
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    // int i = 1;
    // cin >> t;
    while (t--) {
        // cout << "Case #" << i << ": ";
        solve();
        // i++;
    }
    return 0;
}
Leave a Comment