52 lines
909 B
C++
52 lines
909 B
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
int n;
|
|
long long M;
|
|
vector<long long> w, suf; // suf[i] = w[i] + ... + w[n-1]
|
|
vector<int> x;
|
|
bool found = false;
|
|
|
|
void dfs(int i, long long sum) {
|
|
if (sum > M) return;
|
|
if (sum + suf[i] < M) return; // 就算后面全选也不够
|
|
|
|
if (i == n) {
|
|
if (sum == M) {
|
|
for (int k = 0; k < n; ++k) cout << x[k];
|
|
cout << '\n';
|
|
found = true;
|
|
}
|
|
return;
|
|
}
|
|
|
|
x[i] = 0;
|
|
dfs(i + 1, sum);
|
|
|
|
x[i] = 1;
|
|
dfs(i + 1, sum + w[i]);
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
cin >> n;
|
|
cin >> M;
|
|
|
|
w.resize(n);
|
|
x.assign(n, 0);
|
|
suf.assign(n + 1, 0);
|
|
|
|
for (int i = 0; i < n; ++i) cin >> w[i];
|
|
|
|
for (int i = n - 1; i >= 0; --i) {
|
|
suf[i] = suf[i + 1] + w[i];
|
|
}
|
|
|
|
dfs(0, 0);
|
|
|
|
if (!found) cout << -1 << '\n';
|
|
return 0;
|
|
}
|