Submission #1001388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001388		cowwycow	Bank (IZhO14_bank)	C++14	100 / 100	674 ms	122704 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

int bit(int i, int j){
	return (i >> j) & 1;
}

const int maxlog = 22;
const int maxn = (1 << maxlog) + 5;

int a[maxlog], b[maxlog];

vector<int> masksum[maxn];
int dp[maxn];

void solve(){
	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];
	}
	int lim = (1 << m);
	for(int mask = 1; mask < lim; mask++){
		int sum = 0;
		for(int j = 1; j <= m; j++){
			if(bit(mask, j - 1)){
				sum += b[j];
			}
		}
		masksum[sum].push_back(mask);
	}
	for(int i = 0; i < maxn; i++){
		dp[i] = -1;
	}
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		for(int mask = lim - 1; mask >= 0; mask--){
			if(dp[mask] == -1) continue;
			for(int submask : masksum[a[i]]){
				if(!(submask & mask)){
					dp[submask | mask] = dp[mask] + 1;
					if(dp[submask | mask] == n){
						cout << "YES";
						return;
					}
				}
			}
		}
	}
	cout << "NO";
}

int main(){
  file();
  solve();
}

Compilation message (stderr)

bank.cpp: In function 'void file()':
bank.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen(name".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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