Submission #1134292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134292		Muhammet	Bank (IZhO14_bank)	C++17	71 / 100	1095 ms	768 KiB

bank

#include "bits/stdc++.h"

using namespace std;

int n, m, k;

vector <int> a, b, c, v;

map <pair<int,int>, bool> dp;

void f1(int x, int ind, int y){
	if(x < 0) return;
	if(ind == m){
		if(x == 0) v.push_back(y);
		return;
	}
	if((y>>ind)&1){
		f1(x,ind+1,y);
		return;
	}
	f1(x-b[ind+1],ind+1,y|(1<<ind));
	f1(x,ind+1,y);
}

bool f(int x){
	if(x == n+1) return true;
	if(dp.find({x,k}) != dp.end()) return true;
	v.clear();
	f1(a[x],0,k);
	vector <int> v1 = v;
	for(auto i : v1){
		k = i;
		dp[{x,k}] = true;
		if(f(x+1)){
			dp[{x,k}] = true;
			return true;
		}
	}
	return false;
}

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

	cin >> n >> m;
	a.resize(n+1), b.resize(m+1), c.resize(m+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> b[i];
	}
	cout << (!f(1) ? "NO\n" : "YES\n");
}

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