Submission #499175

#	Time	Username	Problem	Language	Result	Execution time	Memory
499175		Aktan	Bank (IZhO14_bank)	C++17	100 / 100	758 ms	6856 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],dp[1050005];
vector<int> v[100005];
main(){
	int n,m;
	cin >> n >> m;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int j=0;j<m;j++){
		cin >> b[j];
	}
	for(int mask=0;mask<(1<<m);mask++){
		int sum=0;
		for(int j=0;j<m;j++){
			if(mask&(1<<j)){
				sum+=b[j];
			}
		}
		for(int j=0;j<n;j++){
			if(sum==a[j]){
				v[j].push_back(mask);
			}
		}
	}
	dp[0]=1;
	for(int i=0;i<n;i++){
		for(int j=(1<<m);j>=0;j--){
			if(dp[j]>0){
				for(auto it : v[i]){
					if(it&j){
						continue;
					}
					int x=it|j;
					dp[x]=max(dp[x],dp[j]+1);
					if(dp[x]>n){
						cout <<"YES";
						return 0;
					}
				}
			}
		}
	}
	cout << "NO";
}

Compilation message (stderr)

bank.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 | main(){
      | ^~~~

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