제출 #167205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167205		muhammad_hokimiyon	은행 (IZhO14_bank)	C++14	71 / 100	111 ms	10256 KiB

bank

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

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

using namespace std;

const int N = 2e5 + 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";
}

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