Submission #1194537

#TimeUsernameProblemLanguageResultExecution timeMemory
1194537p4r4d0_xBank (IZhO14_bank)C++20
100 / 100
488 ms86144 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back void solve(){ ll n, m; cin >> n >> m; vector<ll> a(n), b(m); for(auto &i : a)cin >> i; for(auto &i : b)cin >> i; vector<vector<ll>> v(1001); vector<vector<bool>> dp((1 << m), vector<bool>(m)); ll sum = 0; for(int mask = 1; mask < (1 << m); ++mask){ sum = 0; for(int i = 0; i < m; ++i){ if(mask & (1 << i)){ sum += b[i]; } } if(sum <= 1000)v[sum].pb(mask); } for(auto &mask : v[a[0]]){ dp[mask][0] = true; } for(int mask = 0; mask < (1 << m); ++mask){ for(int i = 0; i < n - 1; ++i){ if(!dp[mask][i])continue; for(auto&msk:v[a[i+1]]){ if(mask&msk)continue; dp[mask|msk][i+1]=1; } } } for(int mask = 1; mask < (1 << m); ++mask){ if(dp[mask][n - 1]){ cout << "YES\n"; return; } } cout << "NO\n"; } int main(){ solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...