Submission #973957

#	Time	Username	Problem	Language	Result	Execution time	Memory
973957		beksultan04	Bank (IZhO14_bank)	C++14	100 / 100	739 ms	9044 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[30],b[30],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))sum += b[i];
		}
		for (i=0;i<n;++i){
			if (sum == a[i]){
				v[i].pb(mask);
			}
		}
	}
	for (i=0;i<(1<<m);++i){
		dp[i] = -1;
	}
	dp[0] = 0;
	
	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;
						if (dp[mask|x] == n){
							YES
							ret 0;
						}
					}
				}
			}
		}
	}
	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: 29 / 29