Submission #739961

#	Time	Username	Problem	Language	Result	Execution time	Memory
739961		Toxtaq	Bank (IZhO14_bank)	C++17	100 / 100	128 ms	2388 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>people, banknotes;
vector<short>table;
short rec(int indx, int mask, int cur_people){
    if(indx == n)return 1;
    if(cur_people < 0)return 0;
    if(cur_people == 0){
        indx++;
        if(indx == n)return 1;
        cur_people = people[indx];
    }
    bool res = 0;
    if(table[mask] != -1)return table[mask];
    for(int i = 0;i < m;++i){
        if(mask & (1 << i)){
            res = res | rec(indx, mask ^ (1 << i), cur_people - banknotes[i]);
        }
    }
    return table[mask] = res;
}
int main()
{
    cin >> n >> m;
    people.resize(n);
    banknotes.resize(m);
    table.assign((1 << m), -1);
    for(int i = 0;i < n;++i)cin >> people[i];
    for(int i = 0;i < m;++i)cin >> banknotes[i];
    if(rec(0, (1 << m) - 1, people[0])){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

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