Submission #464069

#	Time	Username	Problem	Language	Result	Execution time	Memory
464069		vantablack27	Bank (IZhO14_bank)	C++14	100 / 100	130 ms	8584 KiB

bank

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vll = vector<ll>;
using vi = vector<int>;

#define newl "\n"
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define INF 1e10
#define EPS 1e-9
#define MOD 1000000007
#define FOR(i, j, k, in) for (ll i = j; i < k; i += in)
#define REP(i, j) FOR(i, 0, j, 1)
#define PRINT_VEC(vec)    \
	for (auto x : vec)    \
	{                     \
		cout << x << " "; \
	}                     \
	cout << "\n";
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << " is " << x << newl

string resp[] = {"NO", "YES"};

template <typename T>
T read()
{
	T toRead;
	cin >> toRead;
	assert(cin);
	return toRead;
}

const int MAXN = 25;
int a[MAXN], b[MAXN];
pii dp[1<<MAXN];

void solve()
{
	int n,m;
	cin>>n>>m;

	REP(i,n) cin>>a[i];
	REP(i,m) cin>>b[i];
	
	REP(mask,1<<m) {
		REP(i,m) {
			if ((mask&(1<<i)) == 0) continue;

			int oth=mask^(1<<i);
			int emp=dp[oth].fir, rem=dp[oth].sec;

			if (rem+b[i] == a[emp]) {
				dp[mask] = max(dp[mask], {emp+1, 0});
			} else {
				dp[mask] = max(dp[mask], {emp, rem+b[i]});
			}
		}
	}

	cout << resp[dp[(1<<m)-1].fir == n] << newl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tc=1;
	/* int tc = read<int>(); */
	while (tc--)
	{
		solve();
	}
}

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