Submission #1100386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100386		pb2008	Bank (IZhO14_bank)	C++17	100 / 100	68 ms	4524 KiB

bank

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

const int N = 20 + 5, M = (1 << 20) + 5;
int n, m, a[N], b[N], dp[M], sum[N];

void readInput();
void fillSum();
void fillDP();
void solve();
void writeOutput();

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    readInput();
    solve();
    writeOutput();
    return 0;
}

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

void fillSum() {
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i - 1];
}

void fillDP() {
    for (int i = 1; i < 1 << m; i++) {
        int _sum = 0;
        for (int j = 0; j < m; j++)
            if (i >> j & 1) {
                _sum += b[j];
                dp[i] = max(dp[i], dp[i ^ (1 << j)]);
            }
        if (_sum == sum[dp[i] + 1])
            dp[i]++;
    }
}

void solve() {
    fillSum();
    fillDP();
}

void writeOutput() {
    if (dp[(1 << m) - 1] == n)
        cout << "YES";
    else
        cout << "NO";
}

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