This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
This code belongs to Aadit Ambadkar
Date: 2022-01-25 21:41:41
Problem: bank
*/
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
vector<int> a;
vector<int> b;
int n, m;
bool works = false;
vector<vector<bool>> vis(21, vector<bool>(1048576, false));
void recur(int ly, int cmsk) {
vis[ly][cmsk]=true;
for (int msk = cmsk+1; msk < (1<<m); msk++) {
if ((cmsk & msk) == cmsk) { // learned by thinking
int tmsk = msk ^ cmsk;
int sum = 0;
F0R(i, m) {
if (tmsk & (1<<i)) {
sum+=b[i];
}
if (sum > b[i]) break;
}
if (sum==a[ly]) {
if (ly == n-1) {
cout << "YES\n";
exit(EXIT_SUCCESS);
} else {
if (!vis[ly+1][msk]) {
recur(ly+1, msk);
}
}
}
}
}
}
int main() {
fastio;
cin >> n >> m;
if (n==1) {
int k; cin >> k;
vector<int> arr(m, 0);
F0R(i, m) cin >> arr[i];
sort(arr.begin(), arr.end());
set<int> psbl;
psbl.insert(0);
F0R(i, m)
for (auto it = psbl.rbegin(); it != psbl.rend(); it++) {
psbl.insert((*it)+arr[i]);
}
if (psbl.count(k)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
} else {
int x;
F0R(i, n) {
cin >> x;
a.pb(x);
}
F0R(i, m) {
cin >> x;
b.pb(x);
}
recur(0, 0);
cout << "NO\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |