Submission #1309386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309386		JuanJL	Bank (IZhO14_bank)	C++20	100 / 100	549 ms	172808 KiB

bank

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(); cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <typename L>
using iset = tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update>;

const int MAXX = 21;
const int MAXY = (1LL<<20LL)+5;

const int MAXN = 21;

ll n,m;
ll a[MAXN];
ll b[MAXN];
ll psum[MAXN];

ll dp[MAXX][MAXY];

ll f(ll x, ll y){

	ll &res = dp[x][y];
	if(res!=-1) return res;
	if(x==n) return 0;

	vector<ll> p;
	
	ll sum = 0;
	forn(i,0,m){
		if(!(y&(1<<i))){
			p.pb(i);
		}else{
			sum+=b[i];
		}
	}

	res=0;

	if(sum==psum[x]){
		/*cout<<psum[x]<<'\n';
		cout<<sum<<'\n';
		cout<<x<<" listo : "; forn(j,0,m) cout<<(y&(1<<j)?1:0)<<" "; cout<<'\n';*/
		res=max(res,f(x+1,y)+1);
		return res;
	}

	for(auto i:p) if(b[i]+sum<=psum[x]){
		res=max(res,f(x,y|(1<<i)));
	}

	return res;
}

int main(){ FIN;
	cin>>n>>m;
	forn(i,0,n) cin>>a[i];
	forn(j,0,m) cin>>b[j];

	forn(i,0,n) psum[i]=a[i]+(i-1>=0?psum[i-1]:0);

	mset(dp,-1);

	if(f(0,0)==n){
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
	return 0;
}

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