Submission #1229079

#TimeUsernameProblemLanguageResultExecution timeMemory
1229079darkdravenBank (IZhO14_bank)C++20
100 / 100
431 ms38440 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 2e5 + 1; #define nl "\n" #define sp " " #define name "test" #define int long long int n, m,tmp; int a[21], b[21], val[(1<<20) + 1]; bool dp[21][(1<<20)+1]; vector<int> v[N]; signed main() { ios::sync_with_stdio(0); cin.tie(0); //freopen(name".INP", "r", stdin); //freopen(name".OUT", "w", stdout); 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++){ for(int i = 0; i<m; i++){ if(mask & (1<<i)) val[mask] += b[i]; } v[val[mask]].push_back(mask); } for(auto i:v[a[0]]) dp[0][i] = 1; tmp=a[0]; for(int i = 1; i<n; i++){ tmp+=a[i]; for(int mask = 0; mask<(1<<m); mask++){ if(val[mask]!=tmp)continue; for(auto j:v[a[i]]){ if( (mask & j) != j) continue; int m2 = mask^j; dp[i][mask] = max(dp[i][mask], dp[i-1][m2]); } } } for(int mask = 0; mask<(1<<m); mask++) if(dp[n-1][mask]){ cout << "YES"; return 0; } cout << "NO"; return 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...