제출 #863443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863443		TheSilentEnigma	은행 (IZhO14_bank)	C++17	100 / 100	138 ms	9044 KiB

bank

#include <bits/stdc++.h>
#define pb push_back
#define dbg(x) cout << "reached here " << x << endl;
#define f first
#define s second
#define ll long long

using namespace std;
typedef pair<int, int> pii;

const int maxn = 21;
int a[maxn], b[maxn], dp[1<<maxn], ps[maxn], sum[1<<maxn];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		ps[i] = ps[i-1] + a[i];
	}

	for (int i = 1; i <= m; ++i)
		cin >> b[i];

	for (int i = 1; i <= (1<<m)-1; ++i)
	{
		int h = i, bit = 1;
		while(h)
		{
			if(h&1)
				sum[i] += b[bit];
			bit++; 
			h /= 2;
		}
	}

	int ans = 0;
	for (int i = 1; i <= (1<<m)-1; ++i)
	{
		for (int j = 0; j < m; ++j)
			if(i & (1<<j))
				dp[i] = max(dp[i], dp[i^(1<<j)]);
		
		if(sum[i] == ps[dp[i]+1])
			dp[i]++;

		ans = max(ans, dp[i]);
	}
	
	if(ans == n)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
		
	return 0;
} 

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