# Untitled

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