Submission #880639

#	Time	Username	Problem	Language	Result	Execution time	Memory
880639		anton	Bank (IZhO14_bank)	C++17	100 / 100	358 ms	18968 KiB

bank

#include<bits/stdc++.h>

using namespace std;
#define int long long

int n, m;
const int MAX_N = 20;
const int MAX_M = 20;

int a[MAX_N], b[MAX_M];

bool dp[MAX_N][(1<<MAX_M)];

signed main(){
    cin>>n>>m;
    vector<vector<int>> oc(n);

    for(int i = 0; i<n; i++){
        cin>>a[i];
    }
    for(int i = 0; i<m; i++){
        cin>>b[i];
    }

    for(int i = 0; i<(1<<m); i++){
        int s= 0;
        for(int k = 0; k<m; k++){
            if((i&(1<<k)) != 0){
                s+= b[k];
            }
        }


        for(int j = 0; j<n; j++){
            if(a[j] == s){
                oc[j].push_back(i);
            }
        }
    }

    for(auto e: oc[0]){
        dp[0][e] = true;
    }

    for(int i = 1; i<n; i++){
        for(int j = 0; j<(1<<m); j++){
            if(dp[i-1][j]){
                for(auto v: oc[i]){
                    if((j&v) == 0){
                        dp[i][j|v] = true; 
                    }
                }
            }
        }
    }

    for(int j = 0; j<(1<<m); j++){
        if(dp[n-1][j]){
            cout<<"YES"<<endl;
            return 0;
        }
        
    }

    cout<<"NO"<<endl;
}

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