Submission #1070774

#TimeUsernameProblemLanguageResultExecution timeMemory
1070774horezusholBank (IZhO14_bank)C++14
19 / 100
1080 ms5716 KiB
#include<bits/stdc++.h> #define F first #define S second #define SZ(x) int((x).size()) const char nl = '\n'; using ll = long long; using namespace std; const int N = 20; bool dp[N][(1 << N)]; int sum[(1 << N)]; int n, m; int a[N], b[N]; void verkefni() { cin >> n >> m; for (int i = 0; i < n; i ++) cin >> a[i]; for (int j = 0; j < m; j ++) cin >> b[j]; for (int mask = 0; mask < (1 << m); mask ++) { int cur = 0; for (int i = 0; i < m; i ++) { if (mask & (1 << i)) { cur += b[i]; } } sum[mask] = cur; } set<int> v; for (int mask = 0; mask < (1 << m); mask ++) { // i = 0 if (sum[mask] == a[0]) { dp[0][mask] = true; v.insert(mask); } } int last = a[0]; for (int i = 1; i < n; i ++) { set<int> cur; for (int mask = 0; mask < (1 << m); mask ++) { for (auto el : v) { if ((mask & el) == el) { if (sum[mask] - last == a[i]) { dp[i][mask] = true; } cur.insert(mask); } } } v = cur; last += a[i]; } // cout << nl; for (int mask = 0; mask < (1 << m); mask ++) { if (dp[n-1][mask]) { cout << "YES"; return ; } } cout << "NO"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tst = 1; // cin >> tst; while (tst --) { verkefni(); cout << nl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...