제출 #1106115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1106115		akzytr	은행 (IZhO14_bank)	C++17	19 / 100	1046 ms	1096 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;
	}

	if(N > M) {
		cout << "NO" << endl;
        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;
			}
		}
		cout << endl;
	} 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