Submission #167206

#TimeUsernameProblemLanguageResultExecution timeMemory
167206muhammad_hokimiyonBank (IZhO14_bank)C++14
100 / 100
367 ms72696 KiB
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e6 + 7;
const int mod = 1e9 + 7;

int n,m;
int a[N];
int b[N];
int d[22][N];
vector < int > v[N];

void foo( int x , int y )
{
    if( x == n ){
        cout << "YES";
        exit(0);
    }
    if( d[x][y] )return;
    d[x][y] = 1;
    for( int i = 0; i < (int)v[x + 1].size(); i++ ){
        if( (y & v[x + 1][i]) == 0 )foo(x + 1 , y | v[x + 1][i]);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    cin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }
    for( int j = 0; j < m; j++ ){
        cin >> b[j];
    }
    for( int i = 1; i < (1 << m); i++ ){
        int sum = 0;
        for( int j = 0; j < m; j++ ){
            if( (i & (1 << j)) )sum += b[j];
        }
        for( int j = 1; j <= n; j++ ){
            if( sum == a[j] )v[j].push_back(i);
        }
    }
    foo(0 , 0);
    cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...