Submission #1323562

#TimeUsernameProblemLanguageResultExecution timeMemory
1323562zhamsh1d1Bank (IZhO14_bank)C++20
100 / 100
144 ms8636 KiB
// Problem: D - Bank
// Contest: Virtual Judge - Day 5, Dp on subsets, dp on subtrees
// URL: https://vjudge.net/contest/789619#problem/D
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define noSuccess t--
#define int long long
#define pb push_back 
#define F first	
#define S second
#define comeback ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(s) s.begin(),s.end()
#define yes "YES\n"
#define no "NO\n"
#define sz size
 
using namespace std;
const int N = 22;
const int maxn = 22;
const int mod = 1e9 + 7;
int dp[(1<<N)];
int n,m;
int a[maxn],b[maxn];
int pref[maxn];
void tryAgain(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i],pref[i]+=pref[i-1]+a[i];
	for(int i=0;i<m;i++) cin>>b[i];
	for(int mask=1;mask<(1<<m);mask++) dp[mask]=-1;
	bool ok = false;
	for(int mask=0;mask<(1<<m);mask++){
		int k = dp[mask];
		if(k == -1) continue;
		int rem=pref[k];
		for(int j=0;j<m;j++){
			if((1<<j) & mask) rem-=b[j];
		}
		// if(mask == 25) cout<<k<<' '<<rem<<'\n';
		if(dp[mask] >= n)	ok = true;
		for(int j=0;j<m;j++){
			if((1<<j) & mask) continue;
			if(b[j] > rem) continue;
			if(b[j] == rem) dp[mask | (1<<j)] = max(dp[mask | (1<<j)], k + 1);
			if(b[j] < rem) dp[mask | (1<<j)] = max(dp[mask | (1<<j)], k);
		}
	}
	cout << (ok ? yes : no) << '\n';
}
signed main(){
  comeback
  // freopen("length.in", "r", stdin);
  // freopen("length.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while(noSuccess){
    tryAgain();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...