Submission #1165468

#TimeUsernameProblemLanguageResultExecution timeMemory
1165468gulmixBank (IZhO14_bank)C++20
100 / 100
500 ms189340 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; using ll = long long; #define all(x) x.begin(), x.end() #define oset tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> int main(){ ios::sync_with_stdio(false); cin.tie(0); //ifstream cin("seating.in"); //ofstream cout("seating.out"); ll n, m; cin >> n >> m; vector<ll> a(n+1); vector<ll> pref(n+1); for(int i = 1; i <= n; i++){cin >> a[i]; pref[i] = pref[i-1] + a[i];} vector<ll> b(m); for(int i = 0; i < m; i++)cin >> b[i]; vector<ll> s(1<<m); for(int i = 0; i < (1 << m); i++){ for(int j = 0; j < m; j++){ if(i & (1 << j))continue; s[i ^ (1 << j)] = s[i] + b[j]; } } vector<vector<ll>> dp(n+1, vector<ll>((1 << m))); dp[0][0] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int k = 0; k < (1 << m); k++){ if(!dp[i][k])continue; if(k & (1 << j))continue; if(s[k] + b[j] - pref[i] == a[i+1]){ dp[i+1][k ^ (1 << j)] = 1; } dp[i][k ^ (1 << j)] = 1; } } } for(int i = 0; i < (1 << m); i++){ if(dp[n][i]){ cout << "YES\n"; return 0; } } cout << "NO\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...