제출 #1272569

#제출 시각아이디문제언어결과실행 시간메모리
1272569kiteyu은행 (IZhO14_bank)C++20
71 / 100
1095 ms4612 KiB
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=20;
int n,m,a[N+5],b[N+5],dp[(1<<N)];
vector<int>g[N+5];

bool cmp(int x,int y){
    return (int)g[x].size()>(int)g[y].size();
}

int main(){
//    freopen("bank.in","r",stdin);
//    freopen("bank.out","w",stdout);
    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<n;++i){
         //   cout<<i<<":\n";
        for(int mask=1;mask<(1<<m);++mask){
            int s=0;
            for(int j=0;j<m;++j)
                if(((mask>>j)&1)) s+=b[j];
            if(s==a[i]){
                g[i].push_back(mask);
                //cout<<mask<<' ';
            }
        }
        //cout<<'\n';
    }
    for(int mask=0;mask<(1<<n);++mask)
        dp[mask]=-1;
    dp[0]=0;
    for(int mask=0;mask<(1<<m);++mask){
//        cout<<mask<<'_'<<dp[mask]<<'\n';

        if(dp[mask]==-1) continue;
        if(dp[mask]==n) return cout<<"YES",0;
//        cout<<mask<<','<<dp[mask]<<":\n";
        for(int i:g[dp[mask]]){
//            cout<<i<<' ';
            if(!(i&mask)) {
//                cout<<i<<'\n';
                dp[mask^i]=max(dp[mask^i],dp[mask]+1);
            }
        }
    }
    cout<<"NO";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...