Submission #1269510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269510		g4yuhg	Burza (COCI16_burza)	C++20	0 / 160	4 ms	8768 KiB

burza

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "subsequence"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}
ll onbit(ll mask, ll i) {
	return mask | (1 << i);
}

ll n, m;
ll a[30], b[30], id[30];
vector<ll> vt[30];

bool cmp(ll u, ll v) {
	return vt[u].size() < vt[v].size();
}

bool cmp2(ll u, ll v) {
	return __builtin_popcount(u) < __builtin_popcount(v);
}

pii f[(1 << 20)];

pii dp(ll mask) {
	if (mask == (1 << m) - 1) {
		return {0, 0};
	}
	if (f[mask].fi != -1) {
		return f[mask];
	}
	pii res = {0, 0};
	for (int j = 1; j <= m; j ++) {
		if (getbit(mask, j - 1) == 1) continue;
		pii xet = dp(onbit(mask, j - 1));
		xet.se += b[j];
		if (xet.se > a[xet.fi + 1]) {
			continue;
		}
		if (xet.se == a[xet.fi + 1]) {
			xet.se = 0;
			xet.fi ++ ;
		}
		if (xet.fi == n) {
			cout << "YES";
			exit(0);
		}
		res = max(res, xet);
	}
	f[mask] = res;
	return res;
}

bool klinh;

signed main(void) {
    faster;
	  
	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 mask = 0; mask < (1 << m); mask ++) {
		f[mask].fi = -1;
	}
	pii ans = dp(0);
	if (ans.fi >= n) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16