Submission #826713

#	Time	Username	Problem	Language	Result	Execution time	Memory
826713		SoulKnight	Bank (IZhO14_bank)	C++17	19 / 100	72 ms	1364 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[1000 * N + 5], s[1000*N + 5];
int n, m;
int a[N], b[N], d[1000 * N + 5];
vector<int> banknote;
queue<pair<int, int>> q;

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

bool check(int x, int which){
    for (auto& u: v[which]) {
        if ((u | x) == x) return true;
    }
    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, idx = -1;
        for (int j = 0; j < LG; j++){
            if ((1 << j) & i) {sum += a[j]; idx = j;}
        }
        if (a[idx] == sum) d[sum] = -1;
        else d[sum] = sum - a[idx];

        s[sum].push_back(i);
        if (d[sum] != 0) banknote.push_back(sum);
    }
    sort(banknote.begin(), banknote.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 << ' ';


    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(banknote.begin(), banknote.end(), sum)) continue;
        // print(i);
        // cout << sum << ln;
        if (d[sum] == -1 || check(i, d[sum])) {
            // for (int j = 0; j < LG; j++){
            //     if ((1 << j) & i) v[sum][j].push_back(i);
            // }
            v[sum].push_back(i);
            // cout << "added" << ln;
        }
    }

    int total = accumulate(a, a+n, 0);
    cout << ((v[total].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: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29