Submission #675658

#	Time	Username	Problem	Language	Result	Execution time	Memory
675658		TheSahib	Bank (IZhO14_bank)	C++14	100 / 100	307 ms	90408 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");

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> salary[i];
    }
    int banknotes[m];
    for (int i = 0; i < m; i++)
    {
        cin >> 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){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

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