Submission #755184

#TimeUsernameProblemLanguageResultExecution timeMemory
755184vjudge1Bank (IZhO14_bank)C++17
100 / 100
184 ms33240 KiB
#include <bits/stdc++.h>
using namespace std;

long long dp[(1<<21)];
long long a[21];
long long b[21];
long long tong[(1<<21)];
long long vt[(1<<21)];
long long thua[(1<<21)];

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    a[n+1]=10000000000;
    for (int i=1;i<=m;i++)
    {
        cin >> b[i];
    }
    dp[0]=1;
    thua[0]=a[1];
    vt[0]=1;
    for (int i=1;i<=(1<<m);i++)
    {
        for (int i2=1;i2<=m;i2++)
        {
            if (!(i&(1<<(i2-1)))) continue;
            tong[i]+=b[i2];
        }
    }
    for (int i=1;i<=(1<<m);i++)
    {
        long long tong2=0;
        for (int i2=1;i2<=n+1;i2++)
        {
            tong2=tong2+a[i2];
            if (tong2>tong[i]) 
            {
                vt[i]=i2;
                thua[i]=tong2-tong[i];
                break;
            }
        }
    }
    for (int i=1;i<=(1<<m);i++)
    {
        for (int i2=1;i2<=m;i2++)
        {
            if (!(i&(1<<(i2-1)))) continue;
            int bit=i^(1<<(i2-1));
            if (dp[bit]==0) continue;
            if (thua[bit]>=b[i2])
            {
                dp[i]=1;
            }
        }
    }
    // cout << vt[9] << " " << thua[9] << " " << tong[9] << " " << dp[9] << '\n';
    for (int i=1;i<=(1<<m);i++)
    {
        if ((dp[i]) and (vt[i]==n+1)) 
        {
            // cout << i << '\n';
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...