제출 #1106105

#제출 시각아이디문제언어결과실행 시간메모리
1106105akzytr은행 (IZhO14_bank)C++17
0 / 100
1041 ms432 KiB
#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() {
	/*
	Problem B: Bank
	Subtask 1: n = 1, Normal knapsack, 1000
	Subtask 2: M <= 10
	*/

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

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

	if(N == 1) {
		bitset<(int)1e4> dp;

		dp[0] = 1;
		for(int i : b) {
			dp |= (dp >> i);
		}
		cout << (dp[a[0]] ? "YES" : "NO");
        return;
	}

	bool ok = 0;
	do {
		int x = 0;
		ll s = 0;
		for(int i = 0; i < M; i++) {
			if(s + b[i] > a[x]) {
				break;
			}
			s += b[i];
			if(s + b[i] == a[x]) {
				x++;
				s = 0;
			}
			if(x == N) {
				ok = 1;
				break;
			}
		}
	} while(next_permutation(b, b + M));
	cout << (ok ? "YES" : "NO") << endl;
}
int main() {
	B();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...