제출 #474853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474853		ismoilov	은행 (IZhO14_bank)	C++14	100 / 100	137 ms	8524 KiB

bank

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void S()
{
	int n, m;
	cin >> n >> m;
	vector <int> a(n), b(m);
	
	for(int i = 0; i < n; i ++)
		cin >> a[i];
	for(int i = 0; i < m; i ++)
		cin >> b[i];
	vector <pair<int, int>> dp(1<<m, make_pair(-1, 0));
	dp[0] = {0, 0};
	for(int mask = 0; mask < (1 << m); mask ++){
		for(int i = 0; i < m; i ++){
			if((mask >> i) & 1){
				auto it = dp[mask ^ (1 << i)];
				if(it.first != -1){
					if(it.second + b[i] == a[it.first])
						it.first ++, it.second = 0;
					else
						if(it.second + b[i] < a[it.first])
							it.second +=b[i];
						else
							it.first = -1, it.second = 0;
					
					dp[mask] = max(dp[mask], it);
				}
			}
		}
		if(dp[mask].first == n){
			cout << "YES";
			return;
		}
	}
	cout << "NO";
}

int main()
{
	IOS;
	/*int t;
	cin >> t;
	while(t --)*/
		S();
}

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