Submission #725264

#	Time	Username	Problem	Language	Result	Execution time	Memory
725264		Peter2017	Bank (IZhO14_bank)	C++14	100 / 100	107 ms	16724 KiB

bank

#include <bits/stdc++.h>
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define fi first
#define se second

using namespace std;

const int N = 22;
const int oo = 1e9;

int n, m;
int a[N], b[N];
pair <int, long long> f[MASK(N)];

int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	for (int i = 0; i < MASK(m); i++)
		f[i] = {-oo, 0};
	f[0] = {0, 0};
	for (int i = 0; i < MASK(m); i++){
		for (int j = 1; j <= m; j++){
			// cout << i << ' ' << j << '\n';
			int mask = BIT(i, j - 1);
			if (mask) continue;
			mask = (i | MASK(j -  1));
			// if (i == 10 && j == 3) cout << f[mask].fi << ' ' << f[mask].se << '\n';
			if (f[mask].fi < f[i].fi){
				f[mask].fi = f[i].fi;
				f[mask].se = f[i].se + b[j];
			}
			if (f[mask].se == a[f[mask].fi + 1] && f[mask].fi + 1 <= n){
				f[mask].se = 0;
				f[mask].fi++;
			}
		}
	}
	for (int i = 0; i < MASK(m); i++){
		// cout << f[i].fi << ' ' << f[i].se << ' ' << i << '\n';
		if (f[i].fi == n) return cout << "YES", 0;
	}
	cout << "NO";
}
//toi chep code :((((

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