Submission #703319

#	Time	Username	Problem	Language	Result	Execution time	Memory
703319		envifly	Bank (IZhO14_bank)	C++17	100 / 100	122 ms	8540 KiB

bank

#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 0
#else
#include "C:\programmingfunnyxd\debug.cpp"
#endif

using namespace std;
const int MOD = 1e9 + 7;
using ll = long long;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

void solve(){
	int n, m; cin >> n >> m;
	vector<int> a(n), b(m);
	for(int& i: a) cin >> i;
	for(int& i: b) cin >> i;
	
	vector<int> dp(1 << m, -1), left(1 << m, -1);
	// stores max prefix
	dp[0] = left[0] = 0;
	for(int j = 0; j < (1 << m); j++){
		for(int i = 0; i < m; i++){
			if(j & (1 << i)){
				int without = j ^ (1 << i);
				if(dp[without] == -1) continue;
				int tot = left[without] + b[i];
				if(tot == a[dp[without]]){
					dp[j] = dp[without] + 1;
					left[j] = 0;
				}
				else if(tot < a[dp[without]]){
					dp[j] = dp[without];
					left[j] = tot;
				}
			}
		}
		if(dp[j] == n){
			puts("YES");
			return;
		}
	}
	puts("NO");
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T = 1;
	// cin >> T;
	for(int _ = 0; _ < T; _++){
		solve();
	}
}

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