제출 #1248893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248893		mbfibat	은행 (IZhO14_bank)	C++20	100 / 100	275 ms	10696 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int a[N], b[N];
int psum[N];

int sum[1 << N];
int pos[1 << N];

bool f[1 << N];
bool g[1 << N];

int n, m;
bool dp(int mask) {
	int i = pos[mask];
	if (i == n)
		return true;
	if (g[mask])
		return f[mask];
	
	bool ok = false;
	for (int j = 0; j < m; j++) {
		if (!(mask >> j & 1)) {
			int nxt_mask = mask | (1 << j);
			if (sum[nxt_mask] > psum[i]) continue;
			ok = ok || dp(nxt_mask);
		}
	}	
	
	g[mask] = true;
	return f[mask] = ok;
}


int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		psum[i] = (i ? psum[i - 1] : 0) + a[i];
	}
	for (int i = 0; i < m; i++) 
		cin >> b[i];
	
	for (int mask = 0; mask < (1 << m); mask++) {
		sum[mask] = 0;
		for (int j = 0; j < m; j++)
			if (mask >> j & 1)
				sum[mask] += b[j];
				
		pos[mask] = n;
		for (int i = 0; i < n; i++)
			if (psum[i] > sum[mask]) {
				pos[mask] = i;
				break;
			}
	}
	cout << (dp(0) ? "YES" : "NO");
}

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