제출 #1088886

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

const int mxa=1010;

int A[25], B[25];
vector<int> Masks[20*mxa];
vector<int> dp[25];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>A[i];
    for(int i=1; i<=m; i++)
        cin>>B[i];
    //pra cada Ai pegar todas as bitmasks possíves
    for(int mask=1; mask<(1<<m); mask++){
        int soma=0;
        for(int i=m-1; i>=0; i--)
            if(mask&(1<<i))
                soma+=B[i+1]; //+1 por ser 1-index
        Masks[soma].push_back(mask);
    }
    /*
    for(int i=1; i<=n && 0; i++){
        cout<<A[i]<<endl;
        for(int mask:Masks[A[i]]){
            //cout<<"  "<<mask<<endl;
            for(int j=m-1; j>=0; j--)
                if((mask&(1<<j)) > 0)
                    cout<<1;
                else
                    cout<<0;
            cout<<endl;
        }
    }
    */
    //pra cada i ir fazedno a sol da proxima
    dp[0].push_back(0);
    for(int i=0; i<n; i++){
        for(int mask:dp[i]){
            //cout<<i<<' '<<mask<<endl;
            for(int next:Masks[A[i+1]]){
                //cout<<"  "<<(mask & next)<<endl;
                if( (mask & next) == 0)
                    dp[i+1].push_back(mask | next);
            }
        }
    }
    //se existe algo em dp[m]
    if(dp[n].size())
        cout<<"YES";
    else
        cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...