Submission #1272569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272569		kiteyu	Bank (IZhO14_bank)	C++20	71 / 100	1095 ms	4612 KiB

bank

#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;
}

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