Submission #752564

#TimeUsernameProblemLanguageResultExecution timeMemory
752564pemguimnBank (IZhO14_bank)C++14
71 / 100
1074 ms16724 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define pb push_back #define gcd __gcd #define endl "\n" #define task "hihi" using namespace std; const int N = 20, MOD = 1e9 + 7, INF = 2e9 + 5; int n, m, a[N], b[N]; pii dp[1 << N]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen(task".inp", "r", stdin); //freopen(task".out", "w", stdout); cin >> n >> m; a[n] = INF; 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++) dp[mask] = {-1, INF}; dp[0] = {0, 0}; bool check = false; for(int mask = 0; mask < (1 << m); mask++){ for(int i = 0; i < m; i++){ if(mask & (1 << i) || dp[mask].first == -1) continue; int nxt = dp[mask].first; if(a[nxt] == dp[mask].second + b[i]){ dp[mask | (1 << i)] = max(dp[mask | (1 << i)], {dp[mask].first + 1, 0}); } else if(dp[mask].second + b[i] < a[nxt]){ dp[mask | (1 << i)] = max(dp[mask | (1 << i)], {dp[mask].first, dp[mask].second + b[i]}); } } if(dp[mask].first == n) check = true; } if(check) cout << "YES"; else 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...