제출 #1100396

#제출 시각아이디문제언어결과실행 시간메모리
1100396AmirmohammadB은행 (IZhO14_bank)C++17
100 / 100
139 ms4680 KiB
// IN THE NAME OF GOD//
#include<bits/stdc++.h>
//#pragma GCC Optimize("Ofast, unroll-loops")
//#pragma GCC Target("avx2, bmi, bmi2, lzcnt, popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 20 + 5, M = (1 << 20) + 10;

int n, m, a[N], b[N], dp[M], partial[N];

void read_input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	partial[0] = a[0];
	for (int i = 1; i < n; i++)
		partial[i] = partial[i - 1] + a[i];
}

void solve() {
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < M - 5; i++) {
		for (int j = 0; j < m; j++) 
			if (i & (1 << j))
				dp[i] = max(dp[i], dp[i - (1 << j)]);
		int ans = 0;
		for (int j = 0; j < m; j++)
			if (i & (1 << j))
				ans += b[j];
		if (i && dp[i] < n - 1 && ans == partial[dp[i] + 1])
			dp[i]++;
	}
	bool flag = false;
	for (int i = 0; i < (1 << m); i++) {
		if (dp[i] == n - 1) {
			flag = true;
//			cout << i << '\n';
		}
	}
	if (flag)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...