Submission #1163279

#TimeUsernameProblemLanguageResultExecution timeMemory
1163279boclobanchat은행 (IZhO14_bank)C++20
100 / 100
94 ms7740 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1048576;
bitset<MAXN> dp,res,mask[22];
int A[22],B[22],sum[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
void convolution(int n)
{
	for(int i=0;i<n;i++) dp|=((dp&mask[i])<<(1<<i));
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,s=0;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>A[i];
	for(int i=0;i<m;i++) cin>>B[i];
	for(int i=1;i<(1<<m);i++) sum[i]=sum[i-(1<<getlog(i))]+B[getlog(i)];
	dp[0]=1;
	for(int i=0;i<m;i++) for(int j=0;j<(1<<m);j++) mask[i][j]=(1-(j>>i)%2);
	for(int i=0;i<n;i++)
	{
		s+=A[i];
		for(int j=0;j<(1<<m);j++) res[j]=(sum[j]==s);
		convolution(m);
		dp&=res;
	}
	for(int i=0;i<(1<<m);i++) if(dp[i]) return cout<<"YES",0;
	cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...