이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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... |