This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
//#define int long long */
#define ll long long
#define fi first
#define se second
#define ve vector
using namespace std;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) x.begin(), x.end()
const int MAXN = 20;
bool dp[MAXN][1 << MAXN];
int a[MAXN], b[MAXN];
signed main(){
int n, m;
cin >> m >> n;
for(int i = 0; i < m; i++)
cin >> b[i];
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < (1 << n); i++){
int sum = 0;
for(int j = 0; j < n; j++)
if((i >> j) & 1){
sum += a[j];
dp[0][i] |= dp[0][i ^ (1 << j)];
}
if(sum == b[0])
dp[0][i] = 1;
}
for(int it = 1; it < m; it++){
for(int i = 0; i < (1 << n); i++){
int sum = 0;
for(int j = 0; j < n; j++)
if((i >> j) & 1){
sum += a[j];
dp[it][i] |= dp[it][i ^ (1 << j)];
}
if(sum == b[it]){
dp[it][i] = dp[it - 1][((1 << n) - 1) ^ i];
}
}
}
if(dp[m - 1][(1 << n) - 1])
cout << "YES\n";
else 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... |