Submission #1158958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158958		ryaminty	Bank (IZhO14_bank)	C++17	71 / 100	1098 ms	86492 KiB

bank

#include <bits/stdc++.h>
using namespace std;

constexpr int mxN=20;
int n, m;
int a[mxN], b[mxN];
int dp[1<<mxN][mxN], can[1<<mxN][mxN];
vector<int>masks[mxN+1];

int calc(int mask){
    int ret=0;
    for (int i=0;i<m;++i)
        ret+=b[i]*((mask>>i)&1);
    return ret;
}

void printt(vector<int>&v){
    for (int i:v)
        cout << i << " ";
    cout << "\n";
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    for (int i=0;i<n;++i)
        cin >> a[i];
    
    for (int i=0;i<m;++i)
        cin >> b[i];
#if 0
    int mask=8;
    for (int i=0;i<m;++i){
        if (mask&(1<<i)){
            cout << (mask&(1<<i)) << "\n";
            int ad=b[i];
            cout << "i: " << i << " ad: " << ad << "\n";
        }
    }

    return 0;
#endif
    for (int i=0;i<(1<<m);++i)
        for (int j=0;j<n;++j)
            can[i][j]=(calc(i)==a[j]);
    
    masks[0].push_back(0);
    for (int i=0;i<n;++i){
        for (int mask:masks[i]){
            int maskInv = (1<<m)-1-mask;
            for (int submask=maskInv;submask;submask=(submask-1)&maskInv){
                if (can[submask][i])
                    masks[i+1].push_back(submask+mask);
            }
        }
    }
    if (masks[n].empty())
        cout << "NO\n";
    else
        cout << "YES\n";

}

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