제출 #333964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333964		limabeans	은행 (IZhO14_bank)	C++17	52 / 100	1081 ms	5484 KiB

bank

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 22;

int n, m;
int a[maxn];
int b[maxn];

bool dp[maxn][1<<20];
int sum[1<<20];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=0; i<m; i++) {
	cin>>b[i];
    }

    for (int mask=0; mask<1<<m; mask++) {
	for (int j=0; j<m; j++) {
	    if (mask>>j&1) sum[mask] += b[j];
	}
    }

    for (int mask=0; mask<1<<m; mask++) {
	dp[0][mask]=true;
    }

    for (int i=1; i<=n; i++) {
	for (int mask=0; mask<1<<m; mask++) {
	    for (int s=mask; ;s=((s-1)&mask)) {
		if (dp[i-1][s] && sum[mask^s]==a[i]) {
		    dp[i][mask]=true;
		}
		if (s==0) break;
	    }
	}
    }

    for (int mask=0; mask<1<<m; mask++) {
	if (dp[n][mask]) out("YES");
    }
    out("NO");
    
    
    return 0;
}

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