제출 #334010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334010		limabeans	은행 (IZhO14_bank)	C++17	100 / 100	696 ms	20828 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 = 21;


int n,m;
int a[maxn];
int b[maxn];
bool dp[maxn][1<<maxn];

vector<int> sum[1010];

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

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


    for (int mask=0; mask<1<<m; mask++) {
	int cur = 0;
	for (int i=0; i<m; i++) {
	    if (mask>>i&1) cur += b[i];
	}
	if (cur > 1000) continue;
	sum[cur].push_back(mask);
    }

    for (int mask: sum[a[0]]) {
	dp[0][mask] = true;
    }

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


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

    out("NO");
    
    
    return 0;
}

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