Submission #167179

#	Time	Username	Problem	Language	Result	Execution time	Memory
167179		Gurban	Bank (IZhO14_bank)	C++11	0 / 100	60 ms	988 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[30],a[30],c,v[1009][35],dp[1009][35],mx;

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

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