제출 #659140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659140		ajab_01	은행 (IZhO14_bank)	C++17	100 / 100	524 ms	9712 KiB

bank

#include<bits/stdc++.h>
using namespace std;

const int N = 21;
vector<int> sub[N];
long long pre[N];
bool dp[(1 << N)] , flg;
long long sm[(1 << N)] , a[N] , b[N] , n , m;

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];
	for(int i = 0 ; i < m ; i++)
		cin >> b[i];
	pre[0] = a[0];
	for(int i = 1 ; i < n ; i++)
		pre[i] = pre[i - 1] + a[i];
	for(int mask = 0 ; mask < (1 << m) ; mask++)
		dp[mask] = 1;
	for(int mask = 0 ; mask < (1 << m) ; mask++)
		for(int i = 0 ; i < m ; i++)
			if(mask & (1 << i))
				sm[mask] += b[i];
	for(int mask = 0 ; mask < (1 << m) ; mask++)
		for(int i = 0 ; i < n ; i++)
			if(sm[mask] == a[i])
				sub[i].push_back(mask);
	for(int i = 0 ; i < n ; i++){
		for(int mask = (1 << m) - 1 ; mask >= 0 ; mask--){
			if(pre[i] == sm[mask]){
				bool ch = 0;
				for(int val : sub[i])
					if((mask & val) == val && dp[mask ^ val])
						ch = 1;
				dp[mask] = ch;
			}
			else{
				dp[mask] = 0;
			}
			if(i == n - 1 && dp[mask])
				flg = 1;
		}
	}

	if(!flg)
		cout << "NO" << '\n';
	else
		cout << "YES" << '\n';
	return 0;
}

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