이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int C = 1010;
vector<int> good[C][21];
bool dp[21][(1 << 21)];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
int a[n], b[m];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
sort(a, a + n), sort(b, b + m);
for (int mask = 0; mask < (1 << m); mask++) {
int sum = 0, bits = 0;
for (int j = 0; j < m; j++)
sum += ((mask >> j) & 1) * b[j], bits += ((mask >> j) & 1);
if (sum < C)
good[sum][bits].emplace_back(mask);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << m); j++)
dp[i][j] = false;
}
for (int bit = 0; bit <= m; bit++)
for (int mask: good[a[0]][bit])
dp[0][mask] = true;
for (int j = 0; j < (1 << m); j++)
for (int bit = 0; bit < m; bit++) {
if (((j >> bit) & 1) == 1 && dp[0][j - (1 << bit)]) {
dp[0][j] = true;
break;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < (1 << m); j++) {
for (int bit = 0; bit < m; bit++) {
if (((j >> bit) & 1) == 1 && dp[i][j - (1 << bit)]) {
dp[i][j] = true;
break;
}
}
int bits = 0;
for (int bit = 0; bit < m; bit++) bits += ((j >> bit) & 1);
if (!dp[i][j]) {
for (int bit = bits; bit >= 0; bit--) {
for (int mask: good[a[i]][bit]) {
if ((j & mask) == mask && dp[i - 1][j - mask]) {
dp[i][j] = true;
break;
}
}
}
}
}
}
cout << (dp[n - 1][(1 << m) - 1] ? "YES" : "NO");
return 0;
}
# | 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... |