제출 #1158961

#제출 시각아이디문제언어결과실행 시간메모리
1158961ryaminty은행 (IZhO14_bank)C++17
71 / 100
1098 ms90812 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int mxN=20;
int n, m;
int a[mxN], b[mxN];
int dp[1<<mxN][mxN], can[1<<mxN][mxN];
int calc_res[1<<mxN];
vector<int>masks[mxN+1];


int calc(int mask){
    if (calc_res[mask])
        return calc_res[mask];
    int ret=0;
    for (int i=0;i<m;++i)
        ret+=b[i]*((mask>>i)&1);
    return calc_res[mask]=ret;
}

void printt(vector<int>&v){
    for (int i:v)
        cout << i << " ";
    cout << "\n";
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    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)
        for (int j=0;j<n;++j)
            can[i][j]=(calc(i)==a[j]);
    
    masks[0].push_back(0);
    for (int i=0;i<n;++i){
        for (int mask:masks[i]){
            int maskInv = (1<<m)-1-mask;
            for (int submask=maskInv;submask;submask=(submask-1)&maskInv){
                if (can[submask][i])
                    masks[i+1].push_back(submask+mask);
            }
        }
    }
    if (masks[n].empty())
        cout << "NO\n";
    else
        cout << "YES\n";

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...