제출 #1089360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089360		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	102 ms	50788 KiB

bank

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = int;
#define f first
#define s second
const ll N=29;
ll n,m,a[N],b[N],ans,used[N][(1<<20)],dp[N];

vector<ll>masks[N];
void dfs(ll v,ll mask){
    used[v][mask]=1;
    if(v==n+1){
        cout<<"YES";
        exit(0);
    }for(ll to:masks[v]){
        if(!(to&mask)&&!used[v+1][mask|to]){
            dfs(v+1,mask|to);
        }
    }

}
void f(ll x,ll sum=0,ll mask=0){
    if(x==m){
        for(ll i=1;i<=n;i++){
            if(sum==a[i])masks[i].push_back(mask);
        }
        return;
    }
    x++;
    f(x,sum+b[x],mask|(1ll<<(x-1)));
    f(x,sum,mask);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;

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

    f(0);
    dfs(1,0);
    cout<<(ans ? "YES" : "NO");
}

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