Submission #1001780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001780		hehebjp123	Bank (IZhO14_bank)	C++14	100 / 100	87 ms	33368 KiB

bank

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<ll,ll>
using namespace std;
const ll mod=1e9+7;
const ll len=21;
ll res=0,mi,gcd=0,d=0,i,n,m,j;
ll a[len],b[len];
ii dp[1<<len];
ii cmp(ii a,ii b)
{
    return (a.fi==b.fi?(a.se<b.se? a:b):(a.fi>b.fi?a:b));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
cin>>n>>m;
for(i=1;i<=n;i++)
    cin>>a[i];
for(i=0;i<m;i++)
    cin>>b[i];
// dp[mask] còn bnh thg cần fill
for(auto &x:dp)
x={-1,-1};
dp[0]={0,a[1]};
//8cout<<cmp(dp[1],dp[0]).fi<<" ";
for(ll mask=0;mask<(1<<m);mask++)
{
    for(ll i=0;i<m;i++)
    if(!(mask&(1<<i)))
    {
       // if(mask==0)cout<<mask<<" "<<(mask|(1<<i))<<'\n';
        if(b[i]<=dp[mask].se)
        {
         if(b[i]==dp[mask].se)
        {
             if(dp[mask].fi==n-1) return cout<<"YES",0;
        dp[mask|(1<<i)]=cmp(dp[mask|(1<<i)],{dp[mask].fi+1,a[dp[mask].fi+2]});
        }
        else
        {
        dp[mask|(1<<i)]=cmp(dp[mask|(1<<i)],{dp[mask].fi,dp[mask].se-b[i]});
        }
        }
    }
}
//cout<<dp[2].fi<<' '<<dp[2].se<<" ";
cout<<"NO";
return 0;
}
// d=ma-mi mi=2*x-ma

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29