Submission #1268549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268549		brinleyhong	Bank (IZhO14_bank)	C++20	71 / 100	1099 ms	86600 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[25], b[25], sum_masks[(1<<20)+5], suffixsum[20+5];
int dp[20+5][(1<<20)+5];
bool cmp (int x, int y)
{
    return x>y;
}
int dfs(int idx, int remmask)
{
    if (idx == n) return 1; //went through all ns
    if (sum_masks[remmask] < suffixsum[idx]) return 0;
    int &v = dp[idx][remmask];
    if (v != -1) return v;
    for (int sub = remmask; sub; sub = (sub-1) & remmask)
    {
        if (sum_masks[sub] == a[idx])
        {
            if (dfs(idx+1, sub^remmask)) return v = 1;
        }
    }
    return v = 0;
}
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 = 0; i<n; ++i)
    {
        for (int j = 0; j<(1<<m); ++j) dp[i][j] = -1;
    }
    int A = 1<<m;
    sort(a, a+n, cmp);
    for (int i = 0; i<A; ++i)
    {
        sum_masks[i] = 0;
        for (int j = 0; j<m; ++j)
        {
            if (i&(1<<j)) sum_masks[i] += b[j];
        }
    }
    suffixsum[n] = 0;
    for (int i = n-1; i>=0; --i)
    {
        suffixsum[i] = suffixsum[i+1] + a[i];
    }
    if (dfs(0, A-1)) cout << "YES";
    else cout << "NO";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
    return 0;
}

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