Submission #884562

#	Time	Username	Problem	Language	Result	Execution time	Memory
884562		White	Bank (IZhO14_bank)	C++14	100 / 100	90 ms	10676 KiB

bank

#pragma GCC optimize ("O3")
#pragma GCC target("sse4.2")
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

int  n,m,ch[22],cash[22];
bool ans=false;
vector<int > hi;
vector<int > num[40004];
bool dad[2000000];

void create(int  bitsm,int  vr,int  ob){
    //cout<<vr<<"ob"<<bitsm<<endl;
    if(vr==m){
        num[ob].push_back(bitsm);
        return;
    }
    create(bitsm,vr+1,ob);
    bitsm =  bitsm + (1 << vr);
    create(bitsm,vr+1,ob+cash[vr]);
}

void solve(int  bitsm,int  vr){
    if(vr==n)ans=true;
    if(ans==true || dad[bitsm]==true)return ;
    dad[bitsm]=true;
    for(int j=num[ch[vr]].size()-1;j>=0 && ans==false;j--){
        int krai = bitsm & num[ch[vr]][j];
        if(krai==0){
            int nov = bitsm + num[ch[vr]][j];
            //cout<<bitsm<<" "<<num[ch[vr]][j]<<"ddd"<<endl;
            solve(nov, vr+1);
        }
    }

}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>ch[i];
    for(int i=0;i<m;i++)cin>>cash[i];

    create(0,0,0);
    solve(0,0);

    if(ans==false)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

    return 0;
}

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