Submission #136601

#	Time	Username	Problem	Language	Result	Execution time	Memory
136601		FedericoS	Bank (IZhO14_bank)	C++14	100 / 100	185 ms	2552 KiB

bank

#include <iostream>
using namespace std;

int N,M;
int A[25],B[25];

bool DP[2000000];
bool V[2000000];

bool F(int b){

	if(V[b])
		return DP[b];

	int S=0;
	for(int j=0;j<M;j++)
		if(b&(1<<j))
			S+=B[j];

	int i=0;
	for(;i<N;i++){
		if(S>=A[i])
			S-=A[i];
		else
			break;
	}

	if(i==N)
		return true;
	int P=A[i]-S;

	bool res=false;
	for(int j=0;j<M;j++)
		if(!(b&(1<<j)) and B[j]<=P)
			res|=F(b|(1<<j));

	DP[b]=res;
	V[b]=true;
	return res;

}

int main(){

	cin>>N>>M;
	for(int i=0;i<N;i++)
		cin>>A[i];
	for(int i=0;i<M;i++)
		cin>>B[i];

	cout<<(F(0)?"YES":"NO");

}

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