競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 289D

 

ABC289D

部分和DP. 移動出来ない場合に注意.
実装するときには,使ってない条件がないか確認しよう.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  ll n, m, k, q;
  cin >> n;
  vll a(n); rep(i,n) { cin >> a[i]; }
  cin >> m;
  set<ll> b;
  rep(i,m){
    ll y; cin >> y;
    b.insert(y);
  }

  ll x ; cin >> x;

  vector<bool> dp(x+1);
  dp[0] = true;
  rep(y, x+1){
    rep(i,n){
      ll z = y + a[i];
      if(z <= x && !in(y, b)) dp[z] = dp[z] | dp[y];
    }
  }
  yesno(dp[x]);

  return 0;
}