제출 #331930

#제출 시각아이디문제언어결과실행 시간메모리
331930vitkishloh228은행 (IZhO14_bank)C++14
0 / 100
3 ms876 KiB
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int maxc = 20000 + 1; int main() { int n, m; cin >> n >> m; vector<int> a(n), b(m); for (int& i : a) cin >> i; for (int& i : b) cin >> i; vector<int> pr(n + 1); for (int i = 0; i < n; ++i) { pr[i + 1] = pr[i] + a[i]; } vector<int> summask((1 << m)); for (int mask = 0; mask < (1 << m); ++mask) { for (int i = 0; i < m; ++i) { if ((mask & (1 << i))) { summask[mask] += b[i]; } } } vector<int> needmask = { 0 }; vector<vector<int>> dp(n, vector<int>(1 << m)); vector<vector<int>> posmask(n + 1); for (int mask = 0; mask < (1 << m); ++mask) { for (int i = 0; i <= n; ++i) { if (summask[mask] == pr[i]) posmask[i].push_back(mask); } } for (int i = 0; i < n; ++i) { int needsum = pr[i]; vector<int> q; for (int mask : posmask[i + 1]) { for (int j = 0; j < m; ++j) { int mask1 = (mask | (1 << j)); if ((i==0 && mask1==0) || (i && dp[i-1][mask1])) { if (summask[mask1] == needsum) { dp[i][mask] = 1; q.push_back(mask); break; } } } } swap(needmask, q); } for (int i = 0; i < (1 << m); ++i) { if (dp[n - 1][i]) { cout << "YES"; return 0; } } cout << "NO"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...