제출 #358541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
358541		nicolaalexandra	은행 (IZhO14_bank)	C++14	100 / 100	267 ms	14572 KiB

bank

#include <bits/stdc++.h>

using namespace std;

short v[22],a[22];
vector <int> L[22];
bool viz[22][1<<21];
int n,m,i,sol;

void back (int pas, int mask){
    if (sol)
        return;
    if (pas > n){
        sol = 1;
        return;
    }

    if (viz[pas][mask])
        return;
    viz[pas][mask] = 1;

    for (auto it : L[pas]){
        if ( (it & mask) == 0)
            back (pas+1,mask | it);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;++i)
        cin>>v[i];

    for (i=0;i<m;++i)
        cin>>a[i];

    int maxi = (1<<m);
    for (int mask=0;mask<maxi;++mask){
        int sum = 0;
        for (int bit=0;bit<m;++bit){
            if (mask & (1<<bit))
                sum += a[bit];
        }

        for (i=1;i<=n;++i){
            if (v[i] == sum)
                L[i].push_back(mask);
        }
    }

    for (i=1;i<=n;++i)
        if (L[i].empty()){
            cout<<"NO\n";
            return 0;
        }

    back (1,0);

    if (sol)
        cout<<"YES";
    else cout<<"NO";


    return 0;
}

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