#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
//ifstream cin("seating.in");
//ofstream cout("seating.out");
ll n, m; cin >> n >> m;
vector<ll> a(n+1);
vector<ll> pref(n+1);
for(int i = 1; i <= n; i++){cin >> a[i]; pref[i] = pref[i-1] + a[i];}
vector<ll> b(m);
for(int i = 0; i < m; i++)cin >> b[i];
vector<ll> s(1<<m);
for(int i = 0; i < (1 << m); i++){
for(int j = 0; j < m; j++){
if(i & (1 << j))continue;
s[i ^ (1 << j)] = s[i] + b[j];
}
}
vector<vector<ll>> dp(n+1, vector<ll>((1 << m)));
dp[0][0] = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < (1 << m); k++){
if(!dp[i][k])continue;
if(k & (1 << j))continue;
if(s[k] + b[j] - pref[i] == a[i+1]){
dp[i+1][k ^ (1 << j)] = 1;
}
dp[i][k ^ (1 << j)] = 1;
}
}
}
for(int i = 0; i < (1 << m); i++){
if(dp[n][i]){
cout << "YES\n";
return 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... |