제출 #536403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536403		blue	은행 (IZhO14_bank)	C++17	100 / 100	126 ms	8540 KiB

bank

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

using vi = vector<int>;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vi A(1+N, 0);
	for(int i = 1; i <= N; i++)
	{
		cin >> A[i];
		A[i] += A[i-1];
	}

	vi b(M, 0);
	for(int j = 0; j < M; j++)
		cin >> b[j];

	vi s((1<<M), 0);

	for(int j = 0; j < M; j++)
		for(int m = 0; m < (1<<M); m++)
			if(m & (1 << j))
				s[m] += b[j];

	vi dp((1<<M), 0);
	dp[0] = 1;

	for(int m = 0; m < (1<<M); m++)
	{
		if(!dp[m]) continue;

		int i = 0;
		while(i+1 <= N && A[i+1] <= s[m])
			i++;

		if(i == N)
		{
			cout << "YES\n";
			return 0;
		}

		for(int z = 0; z < M; z++)
		{
			if(m & (1<<z)) continue;
			if(s[m] + b[z] <= A[i+1])
				dp[m | (1 << z)] = 1;
		}
	}

	cout << "NO\n";
	return 0;
}

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