제출 #318392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318392		Gurban	은행 (IZhO14_bank)	C++17	100 / 100	483 ms	26396 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],x;
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++){
		can[0][i]=1;
		for(int j = 0;j < m;j++) if(i & (1<<j)) sum[i] += b[j];
	}

	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];
			x = j;
			while(x >= 1){
				int now = x&-x;
				can[i][j] |= can[i][j-now];
				x -= now;
			}
			// 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: 29 / 29