Submission #1001385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001385		anHiep	Bank (IZhO14_bank)	C++14	100 / 100	460 ms	24008 KiB

bank

#include<bits/stdc++.h>
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "Orz_chUoNgnn"
#endif
 
using namespace std;
 
#define fi first 
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vi vector<int> 
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 20;
int tc, tt = 1;
 
int n, m;
int a[N + 5], b[N + 5], ps[N + 5];
int sum[(1<<N) + 5];
vi f[N + 5];
bool dp[N + 5][(1<<N) + 5];
ll cal(int j) {
	ll sum = 0;
	for(int k=0; k<m; k++)
		if(1 & (j>>k)) sum += b[k + 1];
	return sum;
}
void solve() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		ps[i] = ps[i - 1] + a[i];
	}
	for(int i=1; i<=m; i++) cin>>b[i];
	for(int i=0; i<(1<<m); i++)
		sum[i] = cal(i);
	for(int i=1; i<=n; i++) {
		for(int j=0; j<(1<<m); j++) 
			if(sum[j] == a[i]) f[i].pb(j);
	}
	dp[0][0] = true;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<(1<<m); j++) {
			if(sum[j] != ps[i]) continue;
			for(auto x: f[i])
				if((j & x) == x) {
			 		dp[i][j] |= dp[i - 1][j xor x];
			 		// if(dp[i - 1][j xor x]) break;
			 	}
			if(dp[n][j]) {
				cout<<"YES";
				return;
			}
		}
	}
	cout<<"NO";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
    for(int tc=1; tc<=tt; tc++) solve();
    cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

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