oj.uz

Submission #675650

# Submission time Handle Problem Language Result Execution time Memory
675650 2022-12-27T15:23:50 Z vjudge1 Bank (IZhO14_bank) C++17
0 / 100
 1 ms 852 KB 
#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) == (mask | m)){
            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";
    }
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -