Submission #1270377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270377		zuz14	Bank (IZhO14_bank)	C++20	71 / 100	1095 ms	536 KiB

bank

#include <bits/stdc++.h>
#define F first
#define S second 
using namespace std;

int n, m;
long long salary[21], bank[21];
vector<int> ok[21];

bool dfs(int k, int mask){
    bool b, res=0;

    //cout<<k<<' '<<mask<<endl;
    if (k>=n || salary[k]==0) return 1;
    if (mask>=(1<<m)-1) return 0;
    for (int i:ok[k]) {
        b=1;
        //cout<<i<<endl;
        for (int j=0; j<m; j++){ 
            if ((i & (1<<j)) && (mask & (1<<j))) b=0;
        }
        //cout<<i<<' '<<b<<' '<<c<<endl;
        if (b) res=max(res, dfs(k+1, mask+i));
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long c;
    cin>>n>>m;
    for (int i=0; i<n; i++) cin>>salary[i];
    for (int i=0; i<m; i++) cin>>bank[i];

    for (int i=0; i<n; i++){
        for (int mask=1; mask<=(1<<m)-1; mask++){
            c=0;
            for (int j=0; j<m; j++) if (mask & (1<<j)) c+=bank[j];
            if (c==salary[i]) ok[i].push_back(mask);
            //cout<<mask<<' '<<c<<endl;
        }
    }

    bool b=dfs(0, 0);
    if (b) cout<<"YES";
    else cout<<"NO";
}

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