Submission #972779

#	Time	Username	Problem	Language	Result	Execution time	Memory
972779		beksultan04	Bank (IZhO14_bank)	C++14	71 / 100	1033 ms	19284 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
const int N = 2048576,INF = 1e9+7;
int a[N],b[N],dp[N];
vector <int> v[30];
main(){
	int n,m,i,j;
	cin>>n>>m;
	for (i=0;i<n;++i)
		cin>>a[i];
	for (j=0;j<m;++j)
		cin>>b[j];
	
	for (int mask = 0;mask < (1<<m); ++mask){
		int sum = 0;
		for (i=0;i<m;++i){
			if ((mask&(1<<i)) != 0){
				sum += b[i];
			}
		}
		for (i=0;i<n;++i){
			if (sum == a[i]){
				v[i].pb(mask);
			}
		}
	}
	for (i=1;i<N;++i)dp[i] = -1;
	for (i=0;i<n;++i){
		for (int mask = (1<<m)-1; mask >= 0;--mask){
			
			if (dp[mask] != -1){
				for (auto x: v[i]){
					if (!(mask&x)){
						dp[mask|x] = dp[mask] + 1;
						
					}
				}
			}
			
		}
	}
	int ans = 0;
	for (int mask = 0; mask <(1<<m);++mask){
		if (dp[mask] == n){
			ans = 1;
		}
	}
	if (ans)YES
	else NO
	
	
	
}

Compilation message (stderr)

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

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