제출 #1163279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163279		boclobanchat	Bank (IZhO14_bank)	C++20	100 / 100	94 ms	7740 KiB

bank

#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";
}

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