#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
ll n, m, arr[25], brr[25], dp[25][(1<<20)];
vector<ll>ms[25];
ll rec(ll i, ll mask){
if(i == 0)
return dp[i][mask] = 1;
if(dp[i][mask] != -1)
return dp[i][mask];
dp[i][mask] = 0;
for(auto it : ms[i]){
if((mask & it) == it)
dp[i][mask] |= rec(i - 1, mask - it);
}
return dp[i][mask];
}
void fun(){
cin>>n>>m;
for(int i = 1; i <= n; i++)cin>>arr[i];
for(int i = 1; i <= m; i++)cin>>brr[i];
for(int i = 1; i < (1 << m); i++){
ll sum = 0;
for(int j = 0; (1 << j) <= i; j++)
if(i & j)
sum += brr[j + 1];
for(int j = 1; j <= n; j++)
if(sum == arr[j])
ms[j].push_back(i);
}
memset(dp, -1, sizeof(dp));
cout<<(rec(n, (1 << m) - 1) == 1 ? "YES\n" : "NO\n");
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int ttt = 1;
//cin>>ttt;
while(ttt--)fun();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
205388 KB |
Output is correct |
2 |
Correct |
75 ms |
205444 KB |
Output is correct |
3 |
Incorrect |
76 ms |
205380 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
76 ms |
205392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
76 ms |
205496 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
205388 KB |
Output is correct |
2 |
Correct |
75 ms |
205444 KB |
Output is correct |
3 |
Incorrect |
76 ms |
205380 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |