Submission #1178213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178213		Bors	Bank (IZhO14_bank)	C++20	71 / 100	1099 ms	82640 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define repf(i,k,n) for(int i=k; i<n; i++)
#define rep(i,n) for(int i=0; i<n; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define all(v) v.begin(), v.end()

typedef long long ll;
typedef vector<int> vi;

const int MAX2N = ((1<<20) + 5), MAXN=20;
int memo[MAX2N][MAXN];

int n,m;
vi a,b;
vector<vi> posibles;

void print(int bm){
	rep(i,m) cout << ((bm>>i)&1);
	cout << '\n';
}
bool dp(int bm, int k){ //puedo ocupar i:=bm_i, tengo que sumar k
	if(k==-1) return true;

	//print(bm);
	int &ans = memo[bm][k];
	if(ans != -1) return ans;

	ans=0;
	for(int pos : posibles[k]){
		//cout << "para sumar " << a[k] << " probando: "; 
		//print(pos); 
		if((bm & pos)==pos) ans |= dp((bm^pos), k-1);
		if(ans) return ans;
	}
	return ans;
	//ver todas las formas en las que puedo sumar k usando esto
	//precomputo? n*2^m
}
//para cada k, veo todas las formas de hacerlo y recomputo
bool sirve(int bm, int k, vi&b){
	int sum=0;
	rep(i,m) if(bm&(1<<i)) sum+=b[i];
	return (sum==k);
}
int main(){ 
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	memset(memo, -1, sizeof memo);
	a.resize(n), b.resize(m);
	rep(i,n) cin>>a[i];
	rep(i,m) cin>>b[i];

	posibles.assign(n, vi());
	rep(i,n){
		rep(bm, (1<<m)){
			if(sirve(bm,a[i],b)) 
				posibles[i].push_back(bm);
		}
	}

	cout << (dp((1<<m)-1, n-1) ? "YES" : "NO")  << '\n';


	return 0;
}

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