제출 #318386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318386		Gurban	Bank (IZhO14_bank)	C++17	71 / 100	1088 ms	13052 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using ll = long long;

const int maxn=22;
const int N = 1<<maxn;
int n,m,a[maxn],b[maxn],sum[N],p[maxn];
bool can[maxn][N],dp[maxn][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i],p[i]=p[i-1]+a[i];
	for(int i = 0;i < m;i++) cin >> b[i];

	for(int i = 0;i < (1<<m);i++)
		for(int j = 0;j < m;j++) if(i & (1<<j)) sum[i] += b[j];

	for(int i = 0;i < (1<<m);i++) can[0][i] = 1;

	for(int i = 1;i <= n;i++){
		for(int j = 0;j < (1<<m);j++) if(sum[j] == p[i]) can[i][j] = can[i-1][j];
		for(int j = 0;j < (1 << m);j++)
			for(int k = 0;k < m;k++) if((1<<k) & j) if(can[i][j-(1<<k)] == 1) can[i][j]=1;
	}
	
	// for(int i = 1;i <= n;i++){
	// 	cout<<i<<" ---> ";
	// 	for(int j = 0;j < (1<<m);j++) if(can[i][j] == 1) cout<<j<<' ';
	// 	cout<<'\n';
	// }

	if(can[n][(1<<m) - 1]) cout<<"YES";
	else cout<<"NO";
}

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