Submission #1262389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262389		buixuia	Bank (IZhO14_bank)	C++17	71 / 100	1093 ms	9712 KiB

bank

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

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