Submission #679296

#	Time	Username	Problem	Language	Result	Execution time	Memory
679296		Hacv16	Bank (IZhO14_bank)	C++17	100 / 100	675 ms	110952 KiB

bank

#include<bits/stdc++.h>
using namespace std;
 
const int MAX = 25;
const int MAXM = 25500;
const int INF = 0x3f3f3f3f;
 
int n, m, a[MAX], b[MAX];
int dp[MAX][(1 << 20) + 5];
vector<int> g[MAXM];

int solve(int i, int mask){ //current index, who I have already used
    if(dp[i][mask] != -1) return dp[i][mask];
    if(i == n + 1) return true;

    int targ = a[i], resp = 0;

    for(auto sub : g[targ]){
        if((sub & mask) != 0) continue;
        if(solve(i + 1, mask | sub)) resp = 1;
    }

    return dp[i][mask] = resp;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
 
    for(int mask = 0; mask < (1 << m); mask++){
        int cur = 0;

        for(int i = 0; i < m; i++)
            if(mask & (1 << i)) cur += b[i];

        g[cur].emplace_back(mask);
    }

    memset(dp, -1, sizeof(dp));
 
    cout << (solve(1, 0) ? "YES" : "NO") << '\n';
 
    return 0;
}

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