Submission #779171

#	Time	Username	Problem	Language	Result	Execution time	Memory
779171		gnhmhp	은행 (IZhO14_bank)	C++14	100 / 100	105 ms	8532 KiB

bank

//oj.uz - IZhO14
#include <bits/stdc++.h>
using namespace std;

const int maxn=(1<<20)+5;
int n, m;
int a[25], b[25], dp[maxn], c[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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 i=1; i<(1<<m); ++i) dp[i]=c[i]=-1;
    for (int mask=1; mask<(1<<m); ++mask)
    {
        for (int i=0; i<m; ++i)
        {
            if (mask&(1<<i))
            {
                int x=mask^(1<<i);
                if (dp[x]==-1) continue;
                int s=c[x]+b[i];
                if (s==a[dp[x]])
                    dp[mask]=dp[x]+1, c[mask]=0;
                else if (s<a[dp[x]])
                    dp[mask]=dp[x], c[mask]=s;
            }
        }
        if (dp[mask]==n)
        {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
}

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