제출 #972793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972793		Aika	은행 (IZhO14_bank)	C++14	100 / 100	962 ms	19276 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define aiiiii ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N=2004876,INF=1e9+7;
int a[N],b[N],dp[N];
vector<int>v[30];
signed main(){
	aiiiii
	int n, m, i, j;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=0;i<m;i++){
		cin>>b[i];
	}
	for(i=0;i<(1<<m);i++){
		int sum=0;
		for(j=0;j<m;j++){
			if((i&(1<<j))!=0){
				sum+=b[j];
			}
		}
		for(j=0;j<n;j++){
			if(sum==a[j])v[j].push_back(i);
		}
	}
	for(i=1;i<N;i++){
		dp[i]=-1;
	}
	for(i=0;i<n;i++){
		for(j=(1<<m)-1;j>=0;j--){
			if(dp[j]!=-1){
				for(auto r:v[i]){
					if(!(j&r)){
						dp[j|r]=dp[j]+1;
					}
					if(dp[j|r]==n){
						cout<<"YES";
						return 0;
					}
				}
			}
		}
	}
	cout<<"NO";
}

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