제출 #970563

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

bank

#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int SMX = 1e3+3;

int dp[1<<21];
int S[1<<21];

signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	vector<int> a(n+1, 0);
	vector<int> b(m);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i]+=a[i-1];
	}
	for(int i = 0; i < m; i++)
		cin >> b[i];
	for(int i = 0; i < m; i++)
		S[1<<i] = b[i];
	for(int i = 0; i < (1<<m); i++)
		S[i] = S[(i&-i)] + S[i-(i&-i)];\
	for(int i = 0; i < (1<<m); i++)
	{
		for(int j = 0; j < m; j++)
		{
			if((i>>j)&1ll)
				dp[i] = max(dp[i], dp[i^(1<<j)]);
		}
		if((dp[i] < n) && (a[dp[i]+1] == S[i]))
			dp[i]++;
	}
	if(dp[(1<<m)-1] == n)
		cout << "YES\n";
	else
		cout << "NO\n";
	return 0;
}	

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