이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int sum[(1 << 20)], dp[(1 << 20)];
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], pref[n];
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) pref[i] = a[i] + (i > 0 ? pref[i - 1] : 0);
for (int i = 0; i < m; i++) cin >> b[i];
for (int mask = 0; mask < (1 << m); mask++) {
sum[mask] = 0;
for (int bit = 0; bit < m; bit++)
sum[mask] += ((mask >> bit) & 1) * b[bit];
}
for (int mask = 0; mask < (1 << m); mask++) {
dp[mask] = -1;
for (int bit = 0; bit < m; bit++) {
if (((mask >> bit) & 1) == 1)
dp[mask] = max(dp[mask], dp[mask - (1 << bit)]);
}
int i = 0;
while (i < n && pref[i] != sum[mask]) i++;
if (i == n) continue;
if (i == 0) {
dp[mask] = 0;
continue;
}
for (int bit = 0; bit < m; bit++) {
if (((mask >> bit) & 1) == 1 && dp[mask - (1 << bit)] != -1) {
int left = sum[mask - (1 << bit)] - pref[dp[mask - (1 << bit)]] + b[bit];
if (left == a[i]) {
dp[mask] = i;
break;
}
}
}
}
cout << (dp[(1 << m) - 1] == n - 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... |