Submission #675656

#	Time	Username	Problem	Language	Result	Execution time	Memory
675656		TheSahib	Bank (IZhO14_bank)	C++14	0 / 100	1 ms	852 KiB

bank

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9

using namespace std;
const int MAX = 20; 

int n, m; 
int dp[(1 << MAX)][MAX];
int salary[MAX];

vector<vector<int>> valueMasks(25005, vector<int>());

bool f(int mask, int i){
    if(i == n) return true;
    if(dp[mask][i] != -1) return dp[mask][i];

    for(int m:valueMasks[salary[i]]){
        if(mask & m == 0){
            if(f(mask | m, i + 1)){
                dp[mask][i] = true;
                return true;
            }
        }
    }
    dp[mask][i] = false;
    return false;
}

int main(){
    ifstream input("bank.in");
    ofstream output("bank.out");

    input >> n >> m;
    for (int i = 0; i < n; i++)
    {
        input >> salary[i];
    }
    int banknotes[m];
    for (int i = 0; i < m; i++)
    {
        input >> banknotes[i];
    }
    for (int mask = 1; mask < (1 << m); mask++)
    {
        int s = 0;
        for (int i = 0; i < m; i++)
        {
            if(mask & (1 << i)){
                s += banknotes[i];
            }
        }
        valueMasks[s].emplace_back(mask);
    }
    for (int mask = 0; mask < (1 << m); mask++)
    {
        for (int i = 0; i < n; i++)
        {
            dp[mask][i] = -1;
        }
        
    }
    
    bool ans = f(0, 0);
    if(ans){
        output << "YES";
    }
    else{
        output << "NO";
    }
}

Compilation message (stderr)

bank.cpp: In function 'bool f(int, int)':
bank.cpp:20:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   20 |         if(mask & m == 0){
      |                   ~~^~~~

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