제출 #827271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827271		SoulKnight	은행 (IZhO14_bank)	C++17	71 / 100	1072 ms	38456 KiB

bank

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

#define ll long long
#define ln '\n'

const int N = 20;
const int LG = 21;
const ll INF = 5e18;
const int MOD = 998244353;

vector<int> v[(1<<N) + 5], s[1000 * N + 5];
int n, m;
int a[N], b[N];
vector<int> salary;
bitset<1000 * N + 5> seen;

void print(int x){
    bitset<20> y(x);
    cout << y << ln;
}

// bool check(int x, int which){
//     print(x);
//     cout << which << ln;
//     for (auto& u: v[which]) {
//         if ((u | x) == x) {cout << "yes\n";return true;}
//     }
//     cout << "no\n";
//     return false;
// }

void solve(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];


    for (int i = 1; i < (1 << n); i++){
        int sum = 0;
        for (int j = 0; j < LG; j++){
            if ((1 << j) & i) {sum += a[j];}
        }
        if (!seen[sum]) {seen[sum] = 1; salary.push_back(sum);}
        s[sum].push_back(i);
    }
    sort(salary.begin(), salary.end());
    // for (auto& u: s[2]) print(u);
    // for (auto& u: s[8]) print(u);
    // for (auto& u: s[10]) print(u);
    // for(auto& u: banknote) cout << u << ' ' << d[u] << ln;;

    for (int i = 1; i < (1 << m); i++){
        int sum = 0;
        for (int j = 0; j < LG; j++){
            if ((1 << j) & i) {sum += b[j];}
        }
        if (!binary_search(salary.begin(), salary.end(), sum)) continue;
        for (auto& u: s[sum]){
            if (u == (u & -u)) {v[u].push_back(i); continue;}

            bool ok = false;
            for (auto& x: v[u & -u]){
                if ((x | i) == i && !v[u&(u-1)].empty() && binary_search(v[u&(u-1)].begin(), v[u&(u-1)].end(), x ^ i)){
                    ok = true;
                    break;
                }
            }

            if (ok) v[u].push_back(i);
        }
    }

    // for (int i = 1; i < (1 << n); i++){
    //     int sum = 0;
    //     for (int j = 0; j < LG; j++){
    //         if ((1 << j) & i) {sum += a[j];}
    //     }
    //     print(i); cout << sum << ln;
    //     for (auto& u: v[i]) print(u);
    //     cout << ln;
    // }

    // for (auto& u: v[(1<<n)-1]) print(u);


    cout << ((v[(1<<n)-1].empty())? "NO": "YES") << ln;




}




int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);


    // ll T; cin >> T;
    // while (T--){
    //     solve();
    // }

    // init();
    solve();
    return 0;
}

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