Submission #1106155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106155		akzytr	Bank (IZhO14_bank)	C++17	19 / 100	117 ms	16856 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define arr array
#define vec vector
#define sz(a) ((int)(a).size())

void B() {
	/*

	people_covered[s]: = I| First I-1 have been covered, the target is first I
	leftover[s]: How much we have left when we have covered first I
	*/

	int N, M;
	cin >> N >> M;

	ll a[N];
	ll b[M];
	for(int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < M; i++) {
		cin >> b[i];
	}

	vector<ll> dp(1 << M, -1);
	vector<ll> leftover(1 << M, -1);
	leftover[0] = 0;
	dp[0] = 0;

	bool flag = 0;
	for(int i = 1; i < (1 << M); i++) {
		for(int lj = 0; lj < M; lj++) {
			if((i >> lj) & 1) {
				int prev = i ^ (1 << lj);
				if(dp[prev] == -1) {
					continue;
				}

				int nc = b[lj];
				dp[i] = dp[prev];

				if(leftover[prev] + nc == a[dp[prev]]) {
					leftover[i] = 0;
					dp[i]++;
				} else {
					leftover[i] = leftover[prev] + nc;
					dp[i] = dp[prev];
				}
				flag = flag || (dp[i] == N);
			}
		}
	}
	cout << (flag ? "YES" : "NO") << endl;
}
int main() {
	B();
}

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