Submission #656380

#	Time	Username	Problem	Language	Result	Execution time	Memory
656380		boykut	Bank (IZhO14_bank)	C++14	71 / 100	1092 ms	9816 KiB

bank

#include <iostream>
#include <vector>

using namespace std;

const int N = 22;
int a[N], b[N], dp[N][1<<N], n, m;
vector<int> can[1001];

int Sum(int mask) {
	int s = 0;
	for (int i = 0; i < m; i++) {
		if ((mask>>i)%2 == 1) s += b[i];
	}
	return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int mask = 0; mask < (1<<m); mask++) {
		int s = Sum(mask);
		if (s <= 1000)
			can[s].push_back(mask);
	}
	
	for (int i = 0; i < can[a[0]].size(); i++)
		dp[0][can[a[0]][i]] = 1;
		
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1<<m); mask++) {
			if (Sum(mask) < a[i]) continue;
			for (int j = 0; j < can[a[i]].size(); j++) {
				int p = can[a[i]][j];
				int False = 0;
				for (int j = 0; j < m; j++) {
					if ((mask>>j)%2 == 0 && (p>>j)%2 == 1) {
						False = 1;
						break;
					}
				}
				if (False == 0) {
					if (dp[i - 1][mask ^ p] == 1)
						dp[i][mask] = 1;
				}
			}
		}
	}
	for (int mask = 0; mask < (1<<m); mask++) {
		if (dp[n-1][mask] == 1)
			return cout << "YES", 0;
	}
	return cout << "NO", 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < can[a[0]].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
bank.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int j = 0; j < can[a[i]].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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