제출 #1001779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001779		kustizus	은행 (IZhO14_bank)	C++17	0 / 100	1 ms	604 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[N+5];
bool dp[N+5][B+5];
void Solve(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        cin>>a[i];
        pre[i]+=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][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[i-1][mask^s]) dp[i][mask]=true;
        }
    for (int i=1;i<mx;++i)
        if (dp[n][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: 0 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29