Submission #968840

#	Time	Username	Problem	Language	Result	Execution time	Memory
968840		HaciyevAlik	Bank (IZhO14_bank)	C++14	100 / 100	300 ms	179168 KiB

bank

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

const int sz=21;
int n,m,a[sz],b[sz],dp[sz][1<<sz];
vector<int> v[1005];

bool solve(int mask,int i) {
    if(i==n) {
        return true;
    }
    if(dp[i][mask]!=-1) {
        return dp[i][mask];
    }
    for(int j=0;j<v[a[i]].size();++j) {
        int cur=v[a[i]][j];
        if((mask&cur)==cur && solve(mask^cur,i+1)==1) {
            return dp[i][mask]=true;
        }
    }
    return dp[i][mask]=false;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;++i) {
        cin >> a[i];
    }
    for(int i=0;i<m;++i) {
        cin >> b[i];
    }
    memset(dp,-1,sizeof(dp));
    for(int mask=0;mask<(1<<m);++mask) {
        int cur=0;
        for(int i=0;i<m;++i) {
            if(mask>>i&1) {
                cur += b[i];
            }
        }
        if(cur>1000) continue;
        v[cur].push_back(mask);
    }
    solve((1<<m)-1,0);
    if(dp[0][(1<<m)-1]) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool solve(int, int)':
bank.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0;j<v[a[i]].size();++j) {
      |                 ~^~~~~~~~~~~~~~~
bank.cpp:18:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   18 |             return dp[i][mask]=true;
      |                    ~~~~~~~~~~~^~~~~
bank.cpp:21:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |     return dp[i][mask]=false;
      |            ~~~~~~~~~~~^~~~~~

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