제출 #1106160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106160		akzytr	Bank (IZhO14_bank)	C++17	100 / 100	110 ms	16976 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;

	vector<int> a(N);
	vector<int> 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;

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

			int nc = b[lj];

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

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