040 - Get More Money（★7）- （非想定解）あるノードが使われるときにそれ以前で満たしているべき条件を100bitのフラグにして、後ろからメモ化再帰 (naoya_t)

040.cc

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128_t LL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define found(s,e)  ((s).find(e)!=(s).end())

int N, W;
vi a;
vvi out;
vector<LL> in;

vi bt(100, 0);
ll best = 0;

map<pair<int,LL>,ll> mm;

ll solve(int ix=N-1, LL mask=0) {
    if (ix == -1) return 0;

    mask &= ((LL)1 << (ix + 1)) - 1;
    pair<int,LL> k(ix, mask);
    if (found(mm, k)) return mm[k];

    if (((mask >> ix) & 1) == 1) {
        return mm[k] = solve(ix-1, mask | in[ix]) + (a[ix] - W);
    } else {
        return mm[k] = max(
                solve(ix-1, mask | in[ix]) + (a[ix] - W),
                solve(ix-1, mask)
        );
    }
}

int main() {
    cin >> N >> W;
    a.resize(N);
    rep(i,N) cin >> a[i];
    out.resize(N); in.resize(N);
    rep(i,N){
        int k; cin >> k;
        out[i].resize(k);
        rep(j,k) {
            cin >> out[i][j]; --out[i][j];
            in[ out[i][j] ] |= ((LL)1 << i);
        }
    }
    rep(i,N){
        for (int j=i-1; j>=0; --j){
            if ((in[i] >> j) & 1) in[i] |= in[j];
        }
    }
    cout << solve() << endl;
    return 0;
}