Submission #167181

#	Time	Username	Problem	Language	Result	Execution time	Memory
167181		Gurban	은행 (IZhO14_bank)	C++11	19 / 100	890 ms	99500 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;
map <int,bool> v[1009];
map <int,bool> dp[1009];

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

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