Submission #1275924

#TimeUsernameProblemLanguageResultExecution timeMemory
1275924nanaseyuzukiBank (IZhO14_bank)C++20
71 / 100
1096 ms8892 KiB
#include <bits/stdc++.h> // Author: Kazuki_Will_Win_VOI_8703 #define fi first #define se second #define pii pair<int, int> #define ll long long #define all(a) a.begin(), a.end() using namespace std; const int mn = 1e6 + 5, bm = (1 << 20) + 1; const int inf = 1e9; int n, a[mn], m, b[mn], sum[mn], dp[mn], ok[mn]; void solve(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= m; i++) cin >> b[i]; for(int mask = 0; mask < (1 << m); mask++){ for(int i = 0; i < m; i++){ if(mask & (1 << i)) sum[mask] += b[i + 1]; } } vector <int> pre, nxt; pre.push_back(0); for(int i = 1; i <= n; i++){ for(auto mask : pre){ int left = ((1 << m) - 1) ^ mask; for(int sub = left; sub; sub = (sub - 1) & left){ if(sum[sub] == a[i]){ if(!ok[mask ^ sub]){ nxt.push_back(mask ^ sub); ok[mask ^ sub] = 1; } } } } for(auto mask : nxt){ ok[mask] = 0; } pre = nxt; nxt.clear(); if(!pre.size()){ cout << "NO\n"; return; } } cout << "YES\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while(t--) solve(); 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...