Submission #1262378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262378		buixuia	Bank (IZhO14_bank)	C++17	71 / 100	1096 ms	5588 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int a[21],b[21],pre[21], sum[(1<<20)+1], pre_idx[20001];
bool dp[(1<<20)+1];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,sum1 = 0,sum2 = 0; cin>>n>>m;
    for(int i = 0; i<n; ++i)cin>>a[i],sum1+=a[i];
    for(int i = 0; i<m; ++i)cin>>b[i],sum2+=b[i];
    if(sum1 > sum2)return cout<<"NO\n",0;
    sort(a,a+n,greater<int>());
    pre[0] = a[0];
    pre[0] = 0;
    for(int i = 0; i < n; i++) pre[i+1] = pre[i] + a[i];
    long long need = pre[n];
    int M = 1<<m;
    for(int mask = 1; mask <M; ++mask){
        int lsb = __builtin_ctz(mask);
        int prev = mask^(1<<lsb);
        sum[mask] = sum[prev] + b[lsb];
    }
    for(int i = 0; i<=20000; ++i)pre_idx[i] = -1;
    for(int i = 0; i<=n; ++i)pre_idx[pre[i]] = i;
    dp[0] = 1;
    for(int mask = 0; mask < M; mask++){
        if(!dp[mask]) continue;
        long long s = sum[mask];
        if(s > 20000) continue;
        int k = pre_idx[s];
        if(k == -1) continue;
        if(k == n)return cout<<"YES\n", 0;
        int rem =(M - 1) ^ mask;
        for(int sub = rem; sub; sub =(sub - 1) & rem){
            if(sum[sub] == a[k]){
                dp[mask | sub] = 1;
            }
        }
    }
    bool ok = 0;
    for(int mask = 0; mask < M; mask++){
        if(dp[mask] && sum[mask] == need){
            ok = 1;
            break;
        }
    }
    cout<<(ok?"YES\n":"NO\n");
    return 0;
}

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