Submission #1001807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001807		kustizus	Bank (IZhO14_bank)	C++17	71 / 100	1074 ms	4844 KiB

bank

#include <bits/stdc++.h>
using namespace std;
const int N=20,B=1048576;
int n,m,a[N+5],b[N+5],pre[N+5],cnt[B+5];
vector <bool> dp(B+5),dp1(B+5);
void Solve(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    for (int i=1;i<=m;++i) cin>>b[i];
    int mx=(1<<m);
    for (int i=1;i<mx;++i)
        for (int j=0;j<m;++j)
            if ((i>>j)&1) cnt[i]+=b[j+1];
    dp[0]=true;
    for (int i=1;i<=n;++i){
        for (int mask=1;mask<mx;++mask){
            if (pre[i]!=cnt[mask]) continue;
            for (int s=mask;s;s=(s-1)&mask){
                if (cnt[s]==a[i] && dp[mask^s]) dp1[mask]=true;
                if (dp1[mask]) break;
            }
        }
        dp=dp1;
        for (int mask=0;mask<mx;++mask) dp1[mask]=false;
    }
    for (int i=1;i<mx;++i)
        if (dp[i]){
            cout<<"YES";
            return;
        }
    cout<<"NO";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
}

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