Submission #890329

#TimeUsernameProblemLanguageResultExecution timeMemory
890329ByeWorldBank (IZhO14_bank)C++14
100 / 100
85 ms8756 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define bupol __builtin_popcount #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; const int MAXN = (1<<20)+5; const int LOG = 20; const int MOD = 1e9+7; const int SQRT = 520; typedef pair<int,int> pii; typedef pair<int,pii> ipii; int n, m; int a[25], b[25]; int dp[MAXN], le[MAXN]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=0; i<m; i++) cin >> b[i]; memset(dp, -1, sizeof dp); dp[0] = 0; le[0] = 0; for(int mask=1; mask<(1<<m); mask++){ for(int i=0; i<m; i++){ if((mask>>i) & 1){ int pre = mask ^ (1<<i); int prans = dp[pre]; if(le[pre]+b[i] == a[prans+1]){ dp[mask] = prans+1; le[mask] = 0; } else if(le[pre]+b[i] < a[prans+1]){ dp[mask] = prans; le[mask] = le[pre]+b[i]; } } } if(dp[mask] == n){ cout << "YES\n"; exit(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...