# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1228914 | hgia | Bank (IZhO14_bank) | C++20 | 1 ms | 320 KiB |
#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,m,ans;
int val[(1<<N)+5],dp[N+5][(1<<N)+5],pre[N+5];
int a[25],b[25];
int main()
{
freopen("bank.in","r",stdin);
freopen("bank.out","w",stdout);
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;
}
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++){
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)
{
mask=(1<<n);
i=n;
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;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |