Submission #1103634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103634		vjudge1	Bank (IZhO14_bank)	C++14	19 / 100	148 ms	32712 KiB

bank

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define IOS      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F        first
#define S        second
#define sz(x)    x.size()
#define all(x)   x.begin(), x.end()
#define pb       push_back

const int Inf    = 2e9 + 10;
const int Mod    = 1e9 + 7;
const int LG     = 25;
const int SQ     = 400;
const int Alpha  = 27;
const int maxN   = 25;
const int maxL   = 2e6;
const int maxS   = 4e4 + 10;

int a[maxN];
int b[maxN];
bool dp[maxL][maxN];

vector <int> sum[maxS];

vector <int> ConvertBinary(int x) {
	vector <int> ret;
	while(x) {
		ret.pb(x%2);
		x/=2;
	}
	return ret;
}

int main() {
	IOS;
	
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++)
		cin >> b[i];

	for(int i = 0; i < (1 << m); i++) {
		vector <int> bin = ConvertBinary(i);
		int s = 0;
		for(int j = 0; j < sz(bin); j++) {
			s += b[j+1] * bin[j];
		}
		sum[s].pb(i);
	}

	for(int j = 1; j < (1 << m); j++) {
		for(int k : sum[a[1]]) {
			if(k|j == j)
				dp[j][1] = true;
		}
	}

	for(int i = 2; i <= n; i++) {
		for(int j = 1; j < (1 << m); j++) {
			for(int k : sum[a[i]]) {
				if(k|j == j) {
					dp[j][i] = dp[j-k][i-1];
				}
			}
		}
	}

	if(dp[(1 << n)-1][n])
		cout << "YES\n";
	else
		cout << "NO\n";

	


}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int j = 0; j < sz(bin); j++) {
      |                    ^
bank.cpp:62:11: warning: self-comparison always evaluates to true [-Wtautological-compare]
   62 |    if(k|j == j)
      |         ~ ^~ ~
bank.cpp:62:11: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   62 |    if(k|j == j)
      |         ~~^~~~
bank.cpp:70:12: warning: self-comparison always evaluates to true [-Wtautological-compare]
   70 |     if(k|j == j) {
      |          ~ ^~ ~
bank.cpp:70:12: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   70 |     if(k|j == j) {
      |          ~~^~~~

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