Submission #1088886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088886		sxwuel	Bank (IZhO14_bank)	C++17	71 / 100	626 ms	262144 KiB

bank

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

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