| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1047629 | manhlinh1501 | 은행 (IZhO14_bank) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 21;
#define ALL(a) (a).begin(), (a).end()
int N, M;
int a[MAXN];
int b[MAXN];
namespace subtask {
bool dp[MAXN][1 << MAXN];
int sum[1 << MAXN];
void solution() {
for(int mask = 0; mask < (1 << M); mask++) {
for(int j = 0; j < M; j++) {
if(mask >> j & 1)
sum[mask] += b[j + 1];
}
}
if(n == 1) {
for(int mask = 0; mask < (1 << M); mask++) {
if(a[n] == sum[mask]) return cout << "YES", void(0);
}
cout << "NO";
exit(0);
}
dp[0][0] = true;
for(int i = 1; i <= N; i++) {
for(int mask = 0; mask < (1 << M); mask++) {
int nmask = ((1 << M) - 1) ^ mask;
for(int smask = nmask; smask > 0; smask = (nmask & (smask - 1))) {
if(sum[smask] == a[i])
dp[i][mask ^ smask] |= dp[i - 1][mask];
}
}
}
for(int mask = 0; mask < (1 << M); mask++) {
if(dp[N][mask]) return cout << "YES", void(0);
}
cout << "NO";
exit(0);
}
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int i = 1; i <= M; i++) cin >> b[i];
if(accumulate(a + 1, a + N + 1, 0) > accumulate(b + 1, b + M + 1, 0))
return cout << "NO", 0;
subtask::solution();
return (0 ^ 0);
}