제출 #659137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659137		ajab_01	은행 (IZhO14_bank)	C++17	0 / 100	1 ms	340 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)];
int 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 < n ; 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 = 0 ; mask < (1 << m) ; 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;
			}
		}
	}

	bool ch = 0;
	for(int i = 0 ; i < (1 << m) ; i++)
		if(dp[i])
			ch = 1;
	if(!ch)
		cout << "NO" << '\n';
	else
		cout << "YES" << '\n';
	return 0;
}

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