제출 #167185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167185		Gurban	은행 (IZhO14_bank)	C++11	19 / 100	67 ms	8364 KiB

bank

 #include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2

using namespace std;

int n,m,b[40],a[40],c,mx,v[22][1 << 22],dp[22][1 << 22];

void bit(int pos,int val){
	if(pos == m){
		int sum = 0;
		for(int i = 0;i < m;i++)
			if((1 << i) & c) 
				sum += b[i];
		if(sum == a[val]) v[val][c] = 1;
		return;
	}
	for(int i = 0;i < 2;i++){
		if(i == 1)
			c |= (1 << pos);
		bit(pos + 1,val);
		c ^= (1 << pos);
	}
}

int main()
{
	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 i = 1;i <= n;i++){
		c = 0;
		bit(0,i);
	}
	mx = (1 << m) - 1;
	for(int i = 0;i < mx;i++) 
		if(v[1][i])
			dp[1][i] = 1;
	for(int i = 2;i <= n;i++){
		for(int j = 0;j < mx;j++){
			if(v[i][j] == 1){
				dp[i][j] = dp[i - 1][mx ^ j];
			}
		}
	}
	for(int i = 0;i < mx;i++){
		if(dp[n][i])
			return cout << "YES\n",0;
	}
	cout << "NO\n";
}

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