Submission #548893

#	Time	Username	Problem	Language	Result	Execution time	Memory
548893		Blossomstream	Bank (IZhO14_bank)	C++14	71 / 100	437 ms	262144 KiB

bank

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int a[1000];
int b[1000];
vector<int> d1[1024];
vector<int> d2[1024];
ll sum[1<<20];
int main() {
    //freopen("bank.in", "r", stdin);
    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 = 0; i < (1<<m); i++) {
        for(int j = 0; (1<<j) <= i; j++) {
            if((i & (1<<j)) != 0) sum[i] += (ll) b[j];
        }
    }
    int x = (n + 1)/2;
    int y = n/2;
    for(int i = 0; i < x; i++) {
        for(int j = 0; j < (1<<m); j++) {
            if(sum[j] == ((ll) a[i])) d1[1<<i].push_back(j);
        }
    }
    d1[0].push_back(0);
    for(int i = 1; i < (1<<x); i++) {
        for(int j = 0; (1<<j) <= i; j++) {
            if(i == (1<<j)) continue;
            if((i & (1<<j)) != 0) {
                for(int l: d1[1<<j]) {
                    for(int k: d1[i - (1<<j)]) {
                        if((l & k) == 0) d1[i].push_back(l + k);
                    }
                }
            }
        }
    }
    for(int i = 0; i < y; i++) {
        for(int j = 0; j < (1<<m); j++) {
            if(sum[j] == ((ll) a[i + x])) d2[1<<i].push_back(j);
        }
    }
    d2[0].push_back(0);
    for(int i = 1; i < (1<<y); i++) {
        for(int j = 0; (1<<j) <= i; j++) {
            if(i == (1<<j)) continue;
            if((i & (1<<j)) != 0) {
                for(int l: d2[1<<j]) {
                    for(int k: d2[i - (1<<j)]) {
                        if((l & k) == 0) d2[i].push_back(l + k);
                    }
                }
            }
        }
    }
    for(int i: d1[(1<<x) - 1]) {
        for(int j: d2[(1<<y) - 1]) {
            if((i & j) == 0) {
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";
}

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