Submission #1228970

#TimeUsernameProblemLanguageResultExecution timeMemory
1228970hgiaBank (IZhO14_bank)C++20
0 / 100
8 ms1864 KiB
#include <bits/stdc++.h> using namespace std; const int N=20; int n,m,ans; int val[(1<<20)+5],dp[21][(1<<20)+5],pre[21]; int a[21],b[21]; vector<int>pos[1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; 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++) { int sum=0; for(int j=0;j<m;j++)if(mask&(1<<j))sum+=b[j]; val[mask]=sum; pos[sum].push_back(mask); } for(int i=0;i<n;i++)for(int mask=0;mask<(1<<m);mask++) { dp[i][mask]=-1; if(i==0&&val[mask]==a[i])dp[i][mask]=1; } pre[0]=a[0]; for(int i=1;i<n;i++) { pre[i]=pre[i-1]+a[i]; for(int mask=0;mask<(1<<m);mask++){ bool check=true; if(val[mask]==pre[i]) { for(int mask1=mask;mask1>0;mask1=(mask1-1)&mask) { if(val[mask1]==a[i]) { dp[i][mask]=max(dp[i][mask],dp[i-1][(mask^mask1)]); } if(dp[i][mask]==1) break; } } } } for(int mask=0;mask<(1<<m);mask++)ans=max(ans,dp[n-1][mask]); if(ans==1)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...