Submission #440041

#	Time	Username	Problem	Language	Result	Execution time	Memory
440041		Autron	Bank (IZhO14_bank)	C++14	100 / 100	136 ms	8544 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int dp[1<<20], lef[1<<20];

int main(){
	int n, m;
	cin>>n>>m;
	vector<int> a(n), b(m);
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	for(int i=0;i<m;++i){
		cin>>b[i];
	}
	for(int mask=1;mask<(1<<m);++mask){
		dp[mask]=-1e9;
		for(int bit=0;bit<m;++bit){
			if(!(mask&(1<<bit))) continue;
			int pmask=mask^(1<<bit);
			if(dp[pmask]<0) continue;
			int val=lef[pmask]+b[bit];
			if(val<a[dp[pmask]]){
				dp[mask]=dp[pmask];
				lef[mask]=val;
			}
			else if(val==a[dp[pmask]]){
				dp[mask]=dp[pmask]+1;
				lef[mask]=0;
			}
		}
		if(dp[mask]==n){
			cout<<"YES\n";
			return 0;
		}
	}
	cout<<"NO\n";
	return 0;
}

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