test/aoj/alds1/alds1_5_a.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A

Depends on

Exhaustive Search (bit 全探索) (lib/others/exhaustive_search.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/others/exhaustive_search.hpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<long long> s = sum_subsets(a);
    vector<int> check(4001);
    for(auto x : s) check[x] = 1;
    int q; cin >> q;
    while(q--){
        int m; cin >> m;
        if(check[m]){
            cout << "yes" << "\n";
        }else{
            cout << "no" << "\n";
        }
    }
}

#line 1 "test/aoj/alds1/alds1_5_a.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/others/exhaustive_search.hpp"

/**
 * @brief Exhaustive Search (bit 全探索)
 * @docs docs/others/exhaustive_search.md
 */

template<typename T>
vector<long long> sum_subsets(T a){
    vector<long long> res;
    int n = a.size();
    for(int bit = 0; bit < (1 << n); bit++){
        long long sum = 0;
        for(int i = 0; i < n; i++){
            int mask = 1 << i;
            if(bit & mask){
                sum += a[i];
            }
        }
        res.emplace_back(sum);
    }
    return res;
}
#line 6 "test/aoj/alds1/alds1_5_a.test.cpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<long long> s = sum_subsets(a);
    vector<int> check(4001);
    for(auto x : s) check[x] = 1;
    int q; cin >> q;
    while(q--){
        int m; cin >> m;
        if(check[m]){
            cout << "yes" << "\n";
        }else{
            cout << "no" << "\n";
        }
    }
}