Submission #369509

#	Time	Username	Problem	Language	Result	Execution time	Memory
369509		MilosMilutinovic	Bank (IZhO14_bank)	C++14	44 / 100	1094 ms	492 KiB

bank

#include <bits/stdc++.h>
using namespace std;
const int N=25;
const int M=1050;
int n,m,a[N],b[N];
void SolveDP(){
	vector<bool> can(M,false);
	can[0]=true;
	for(int i=1;i<=m;i++){
		vector<bool> tmp(M,false);
		for(int j=b[i];j<M;j++)if(can[j-b[i]])tmp[j]=true;
		for(int j=b[i];j<M;j++)if(tmp[j])can[j]=true;
	}
	if(can[a[1]])printf("YES");
	else printf("NO");
}
void SolveBruteForce(){
	vector<int> p(m);
	iota(p.begin(),p.end(),1);
	do{
		//for(int i:p)cout<<i<<" ";
		//puts("");
		bool ok=true;
		int sum=0,j=1;
		for(int i:p){
			sum+=b[i];
			if(sum==a[j]){
				sum=0,j++;
			//	printf("NEKI BUG");
			}
			if(j>n)break;
			if(sum>a[j]){
				ok=false;
				break;
			}
		}
		if(ok){
			printf("YES");
			return;
		}
	}while(next_permutation(p.begin(),p.end()));
	printf("NO");
}
int main(){
	scanf("%i%i",&n,&m);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	for(int i=1;i<=m;i++)scanf("%i",&b[i]);
	//sort(a+1,a+n+1);
	//sort(b+1,b+m+1);
	if(n==1){SolveDP();return 0;}
	if(n<=10)SolveBruteForce();
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%i%i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
bank.cpp:46:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                       ~~~~~^~~~~~~~~~~~
bank.cpp:47:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  for(int i=1;i<=m;i++)scanf("%i",&b[i]);
      |                       ~~~~~^~~~~~~~~~~~

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