Submission #863453

#	Time	Username	Problem	Language	Result	Execution time	Memory
863453		grate	Bank (IZhO14_bank)	C++17	0 / 100	0 ms	600 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pll pair<ll, ll>
#define ppll pair<pll, ll>
#define fll(i, n) for (ll i =0 ; i < n; i++)
#define vll vector<ll>
#define prtv(V) fll(i, V.size()) cout << V[i] << " "; cout << '\n';
ll INF = 2e18;
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll n, m;
	cin >> n >> m;
	vll A(n), B(m); fll(i, n) cin >> A[i];
	ll S = 0;
	fll(i, m) { cin >> B[i]; S += B[i]; }
	sort(B.begin(), B.end(), [](ll a, ll b) { return a > b; });

	vector<pll> ans(1<<n, {0, INF});
	ans[0] = {m, 0};

	fll(s, (1<<n))
	{
		fll(i, n)
		{
			if (!(s&(1<<i)))
			{
				ll sum = 0, j = 0;
				ll k = ans[s].second;
				ll remNotes = ans[s].first;
				while (j < m && A[i] > sum)
				{
					if ((k & (1<<j) )|| (B[j]+sum > A[i]))
					{
						j++;
						continue;
					}
					sum += B[j];
					remNotes--;
					k = k & (1<<j);
					j++;
				}
				if (sum < A[i]) continue;
				if (ans[s|(1<<i)].first < remNotes)
					ans[s|(1<<i)] = {remNotes, k};
			}
		}
	}
	if (ans[(1<<n)-1].second == INF) cout << "NO\n";
	else cout << "YES\n";
}

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