Submission #1013346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013346		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	185 ms	604 KiB

bank

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
#pragma GCC optimize("Ofast")
void YES()
{
    cout<<"YES\n";
}
void NO()
{
    cout<<"NO\n";
}
vector<ll> b;
ll n,m;
ll calc(ll mask)
{
	ll answer = 0;
	for (ll e = 0;e<m;e++)
	{
		if ((1 << e) & mask) answer += b[e];
	}
	return answer;
}
void ans()
{
	cin>>n>>m;
	vector<ll> a(n);
	b = vector<ll>(m);
	vector<bool> dp((1 << m));
	vector<ll> pref(n+1);
	for (ll e = 0;e<n;e++)
	{
		cin>>a[e];
		pref[e] = (e > 0 ? pref[e-1] : 0) + a[e];
	}
	pref[n] = 1e18;
	ll s = 0;
	for (ll e = 0;e<m;e++)
	{
		cin>>b[e];s += b[e];
	}
	if (s < pref[n-1])
	{
		NO();
		return;
	}
	dp[0] = 1;
	for (ll len = 0;len < m;len++)
	{
		for (ll mask = 0;mask < (1 << m);mask++)
		{
			if (__builtin_popcount(mask) != len || !dp[mask]) continue;
			// cout<<mask<<" ";
			ll S = calc(mask);
			ll next = 0;
			for (ll i = 0;i<=n;i++)
			{
				if (pref[i] > S)
				{
					next = i;
					break;
				}
			}
			// cout<<S<<" "<<next<<"\n";
			for (ll pos = 0;pos<m;pos++)
			{
				if (!((1 << pos) & mask) && b[pos]+S <= pref[next])
				{
					dp[mask ^ (1 << pos)] = 1;
				}
			}
		}
	}
	if (dp[(1 << m)-1]) YES();
	else NO();
}
int main()
{
    cin.tie(0);cout.tie(0);
    ios_base::sync_with_stdio(0);
	ll t = 1;
	for (ll e = 1;e<=t;e++)
	{
		ans();
	}
    return 0;
}

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