제출 #1252271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252271		mbfibat	Bank (IZhO14_bank)	C++20	19 / 100	139 ms	12756 KiB

bank

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, m; cin >> n >> m;
	vector<int> a(n), b(m);
	
	for (int& v : a) cin >> v;
	for (int& v : b) cin >> v;	
	
	vector<int> psum(n, 0);
	for (int i = 0; i < n; i++)
		psum[i] = (i > 0 ? psum[i - 1] : 0) + a[i];
	
	vector<int> mpos(1 << m, n);
	vector<int> msum(1 << m, 0);
	for (int mask = 0; mask < (1 << m); mask++) {
		for (int i = 0; i < m; i++) {
			if (mask >> i & 1) {
				msum[mask] += b[i];	
			}
		}
		for (int i = 0; i < n; i++)
			if (msum[mask] < psum[i]) {
				mpos[mask] = i;
				break;
			}
	}
	
	vector<int> f(1 << m, 0);
	f[0] = 0;
	
	for (int mask = 0; mask < (1 << m); mask++) {
		int pos = mpos[mask];
		int need_sum = psum[pos];
		for (int i = 0; i < m; i++) {
			if (!(mask >> i & 1)) {
				if (msum[mask | (1 << i)] == need_sum) {
					f[mask | (1 << i)] = pos + 1;					
					if (pos + 1 == n) {
						cout << "YES";
						return 0;
					}
				}
			}
		}
	}
	
	cout << "NO";
}

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