Submission #915386

#	Time	Username	Problem	Language	Result	Execution time	Memory
915386		codefox	Bank (IZhO14_bank)	C++14	100 / 100	355 ms	8672 KiB

bank

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> opt;
vector<int> money;

void determine(int depth, int cash, int state)
{
    if (depth<0)
    {
        if (cash == 0) opt.push_back(state);
        return;
    }
    determine(depth-1, cash, state);
    determine(depth-1, cash-money[depth], state+(1<<depth));
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<int> comb(1<<m, 0);
    comb[(1<<m) -1]=1;
    money.assign(m, 0);
    vector<int> people(n);
    for (int i = 0; i < n; i++) cin >> people[i];
    for (int i = 0; i < m; i++) cin >> money[i];
    bool b = 1;
    for (int ele:people)
    {
        opt.clear();
        vector<int> comb2(1<<m, 0);
        determine(m-1, ele, 0);
        for (int i = 0; i < (1<<m); i++)
        {
            if (!comb[i]) continue;
            for (int ele:opt)
            {
                if ((ele & i) == ele) comb2[i-ele] = 1;
            }
        }
        b=0;
        for (int i = 0; i < (1<<m); i++)
        {
            comb[i] = comb2[i];
            if (comb2[i]) b=1;
        }
    }
    if (b) cout << "YES";
    else cout << "NO";
    return 0;
}
    

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