Submission #344641

#	Time	Username	Problem	Language	Result	Execution time	Memory
344641		maskoff	Bank (IZhO14_bank)	C++14	71 / 100	1089 ms	16064 KiB

bank

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

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

void solve2() {
	vector<int> all[N];
	int dp[n + 5][N];
	dp[0][0] = true;

 	for (int mask = 0; mask < (1 << m); mask++) {
 	 	int sum = 0;
 	 	for (int i = 0; i < m; i++) 
 	 	 	if ((1 << i) & mask) sum += b[i + 1];
 	 	for (int i = 1; i <= n; i++) 
 	 	 	if (a[i] == sum) 
 	 	 		all[i].pb(mask);
 	}
 	for (int i = 1; i <= n; i++) {
 	 	for (int j : all[i]) {
 	 	 	for (int mask = 0; mask < (1 << m); mask++) {
 	 	 		if (j & mask) continue;
 	 	 	 	dp[i][mask ^ j] |= dp[i - 1][mask];
 	 	 	}
 	 	}
 	}
 	for (int mask = 0; mask < (1 << m); mask++) if (dp[n][mask]) cout << "YES", exit(0);
 	cout << "NO", exit(0);
}

void solve1() {
	vector<int> dp(N);
	dp[0] = true;
	for (int i = 1; i <= m; i++) {
	 	for (int w = 1000; w >= 0; w--) {
	 		dp[w + b[i]] |= dp[w];
	 	}	
 	}
 	if (dp[a[1]]) cout << "YES", exit(0);
 	else cout << "NO", exit(0);
} 

int main() { 
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	if (n == 1) {
	 	solve1();
      return 0;
	}  
	
	 	solve2();
	
  return 0;
}

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