제출 #656378

#제출 시각아이디문제언어결과실행 시간메모리
656378boykut은행 (IZhO14_bank)C++14
44 / 100
1086 ms4224 KiB
#include <iostream> using namespace std; const int N = 22; int a[N], b[N], dp[N][1<<N], n, m; int Sum(int mask) { int s = 0; for (int i = 0; i < m; i++) { if ((mask>>i)%2 == 1) s += b[i]; } return s; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; } for (int mask = 0; mask < (1<<m); mask++) { if (Sum(mask) == a[0]) dp[0][mask] = 1; } // 2^m * m for (int i = 1; i < n; i++) { for (int mask = 0; mask < (1<<m); mask++) { if (Sum(mask) < a[i]) continue; for (int p = 0; p < (1<<m); p++) { if (Sum(p) == a[i]) { int False = 0; for (int j = 0; j < m; j++) { if ((mask>>j)%2 == 0 && (p>>j)%2 == 1) { False = 1; break; } } if (False == 0) { if (dp[i - 1][mask ^ p] == 1) dp[i][mask] = 1; } } } } } for (int mask = 0; mask < (1<<m); mask++) { if (dp[n-1][mask] == 1) return cout << "YES", 0; } return cout << "NO", 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...