鉄則本 A14 - Four Boxes (2Q, ★5)

半分全列挙の典型問題！

• 問題へのリンク

問題概要

長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。

制約

• 

メモ

「半分全列挙」を用いる。詳細は鉄則本にて。

コード

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    for (int i = 0; i < N; i++) cin >> C[i];
    for (int i = 0; i < N; i++) cin >> D[i];

    vector<int> AB, CD;
    for (auto a : A) for (auto b : B) AB.push_back(a + b);
    for (auto c : C) for (auto d : D) CD.push_back(c + d);
    sort(CD.begin(), CD.end());

    bool res = false;
    for (auto ab : AB) {
        auto it = lower_bound(CD.begin(), CD.end(), K - ab);
        if (*it == K - ab) res = true;
    }
    cout << (res ? "Yes" : "No") << endl;
}