제출 #1053737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053737		sssamui	은행 (IZhO14_bank)	C++17	100 / 100	75 ms	8660 KiB

bank

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const int MXN = 20;

int n, m, sz;
vector<int> sal(MXN), nts(MXN);

bool solve()
{
	vector<int> lft(sz, 0), dp(sz, 0);
	for (int i = 0; i < n; i++) cin >> sal[i];
	for (int i = 0; i < m; i++) cin >> nts[i];
	for (int msk = 1; msk < sz; msk++) for (int bit = 0; bit < m; bit++) if (msk & (1 << bit)) if (dp[msk ^ (1 << bit)] >= dp[msk])
	{
		dp[msk] = dp[msk ^ (1 << bit)];
		lft[msk] = lft[msk ^ (1 << bit)] + nts[bit];
		if (lft[msk] == sal[dp[msk]])
		{
			lft[msk] = 0;
			dp[msk]++;
			if (dp[msk] == n) return true;
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	sz = 1 << m;
	cout << (solve() ? "YES" : "NO");
}

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