Submission #1089580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089580		clement1n0t	Bank (IZhO14_bank)	C++17	100 / 100	162 ms	8792 KiB

bank

#include<bits/stdc++.h>

using namespace std;

#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<int,int> pii;

int n,m;
int a[21],b[21];
pii pd[1<<20];


pii solve(int S){
	
	if(S == 0) return {0,0};

	if(pd[S] != make_pair(-1,-1)) return pd[S];

	pd[S] = {0,0};
	for(int i=0;i<m;i++){
		if((S&(1<<i)) == 0) continue;
		
		auto [paid, remain] = solve(S^(1<<i));
		if(paid == n) return {paid, remain};	

		if(a[paid] == remain+b[i]){
			pd[S] = max(pd[S],{paid+1,0});
		}else if(a[paid] > remain+b[i]){
			pd[S] = max(pd[S],{paid,remain+b[i]});
		}	
	}

	return pd[S];
}


int main(){ _
	
	cin >> n >> m;


	for(int i=0;i<n;i++){
		cin >> a[i];
	}

	for(int j=0;j<m;j++){
		cin >> b[j];
	}
	
	fill(pd, pd+(1<<20),make_pair(-1,-1));
	auto [paid, res] = solve((1<<m)-1); 
	
	if(paid == n) cout << "YES\n";
	else cout << "NO\n";

}

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