Submission #1178253

#TimeUsernameProblemLanguageResultExecution timeMemory
1178253Bors은행 (IZhO14_bank)C++20
71 / 100
1095 ms4636 KiB
#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];

int n,m;
vi a,b;
vector<vi> posibles;
map<int,int> mapeando_tonteras;
void print(int bm){
	rep(i,m) cout << ((bm>>i)&1);
	cout << '\n';
}
bool dp(int bm){ //bm_i:=puedo ocupar i, tengo que sumar a_k
	
	int suma_que_llevo=0;
	rep(i,m) if(!((bm>>i)&1)) suma_que_llevo+=b[i];
	int k=mapeando_tonteras[suma_que_llevo];

	//print(bm);
	if(k==n) return true; //complete todo
	//cerr << "tengo que sumar " << a[k] << '\n';
	

	//print(bm);
	int &ans = memo[bm];
	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));
		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 
bool sirve(int bm, int k){
	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];

	{
		int aux=0;
		rep(i,n){
			aux+=a[i];
			mapeando_tonteras[aux] = i+1;
		}
	}

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

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


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...