Submission #1106111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106111		akzytr	Bank (IZhO14_bank)	C++17	19 / 100	41 ms	764 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() {
	/*
	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];
	int g[M];
	for(int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < M; i++) {
		cin >> b[i];
		g[i] = 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;
	}

	sort(b, b + M);
	assert(M <= 10);
	bool ok = 0;
	do {
		int x = 0;
		ll s = 0;
		for(int i = 0; i < M; i++) {
			if(s + b[g[i]] > a[x]) {
				break;
			}
			s += b[g[i]];
			if(s + b[g[i]] == a[x]) {
				x++;
				s = 0;
			}
			if(x == N) {
				ok = 1;
				break;
			}
		}
	} while(next_permutation(g, g + M));
	cout << (ok ? "YES" : "NO") << endl;
}
int main() {
	B();
}

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