Submission #634777

#	Time	Username	Problem	Language	Result	Execution time	Memory
634777		tvladm2009	Bank (IZhO14_bank)	C++14	100 / 100	138 ms	1536 KiB

bank

#include <iostream>

using namespace std;

const int MAX_N = 20;
const int MAX_SUM = 20 * 1e3;
int a[MAX_N + 1], bank[MAX_N + 1], sp[MAX_N + 1];
bool dp[1 << MAX_N];
int spec[MAX_SUM + 1];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sp[i] = sp[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        spec[sp[i]] = i;
    }
    for (int i = 1; i <= MAX_SUM; i++) {
        if (spec[i] == 0) {
            spec[i] = spec[i - 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> bank[i];
    }
    dp[0] = true;
    bool valid = false;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[mask]) {
            int sum = 0;
            for (int bit = 0; bit < m; bit++) {
                if (mask & (1 << bit)) {
                    sum += bank[bit + 1];
                }
            }
            for (int bit = 0; bit < m; bit++) {
                if (!(mask & (1 << bit))) {
                    int mask2 = mask;
                    mask2 |= (1 << bit);
                    int sum2 = sum + bank[bit + 1];
                    if (spec[sum] == spec[sum2]) {
                        dp[mask2] = true;
                    } else if (spec[sum] + 1 == spec[sum2] && sp[spec[sum2]] == sum2) {
                        dp[mask2] = true;
                        if (spec[sum2] == n) {
                            valid = true;
                        }
                    }
                }
            }
        }
    }
    if (valid == true) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

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