Submission #1106157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106157		akzytr	Bank (IZhO14_bank)	C++17	19 / 100	116 ms	16852 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 & (1 << lj)) {
				int prev = i & ~(1 << lj);
				if(dp[prev] == -1) {
					continue;
				}

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

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

Compilation message (stderr)

bank.cpp: In function 'void B()':
bank.cpp:32:7: warning: unused variable 'flag' [-Wunused-variable]
   32 |  bool flag = 0;
      |       ^~~~

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