Submission #1268546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268546		brinleyhong	Bank (IZhO14_bank)	C++20	71 / 100	1096 ms	91112 KiB

bank

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
typedef long long ll;
int n, m, a[maxn+5], b[maxn+5], sum_masks[(1<<maxn)+5], suffixsum[maxn+5];
int dp[maxn+5][(1<<maxn)+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 = 0; sub < (1<<m); ++sub)
    {
        if ((sub & remmask) == sub) {
            if (sum_masks[sub] == a[idx])
            {
                if (dfs(idx+1, remmask^sub)) 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<(1<<m); ++i)
    {
        sum_masks[i] = 0;
        for (int j = 0; j<m; ++j)
        {
            if (i&(1<<j)) sum_masks[i] += b[j];
        }
    }
    suffixsum[n-1] = a[n-1];
    for (int i = n-2; i>=0; --i)
    {
        suffixsum[i] = suffixsum[i+1] + a[i];
    }
    if (dfs(0, (1<<m)-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