Submission #884556

#	Time	Username	Problem	Language	Result	Execution time	Memory
884556		White	Bank (IZhO14_bank)	C++14	71 / 100	1098 ms	34908 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][23];

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][vr]==true)return ;
    for(int z=0;z<=vr;z++)dad[bitsm][z]=true;
    for(int j=0;j<num[ch[vr]].size() && 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);
    cout.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;
}

Compilation message (stderr)

bank.cpp: In function 'void solve(int, int)':
bank.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int j=0;j<num[ch[vr]].size() && ans==false;j++){
      |                 ~^~~~~~~~~~~~~~~~~~~

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