제출 #495818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
495818		maomao90	은행 (IZhO14_bank)	C++17	52 / 100	1094 ms	222020 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int MAXN = (1<<20);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
gp_hash_table<int, short, custom_hash> memo[MAXN];

int N, M, a[21], b[21];

bool dp(int mask, int value, int idx){
    if(idx == N) return true;
    else if(mask == 0) return false;
    if(memo[mask][value] != 0){
        if(memo[mask][value] == 1) return true;
        return false;
    }
    int j = mask;
    while(j){
        int x = j & -j; j -= x;
        int pos = __builtin_ctz(x);
        int nv = value + b[pos];
        if(nv > a[idx]) continue;
        bool result;
        if(nv == a[idx]) result = dp(mask^x, 0, idx+1);
        else result = dp(mask^x, nv, idx);
        if(result){ memo[mask][value] = 1; return true; }
    }
    memo[mask][value] = 2;
    return false;
}

signed main(){
    ios::sync_with_stdio(0);
    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];
    bool res = dp((1<<M)-1, 0, 0);
    if(res) cout << "YES";
    else cout << "NO";
}

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