Submission #168569

#	Time	Username	Problem	Language	Result	Execution time	Memory
168569		mosiashvililuka	Bank (IZhO14_bank)	C++14	100 / 100	356 ms	18040 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,f[1009],g[1009],P[(1<<22)],jm[(1<<22)],s[1009];
bool dp[(1<<22)];
pair <int, int> p[(1<<22)];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=0; i<a; i++) cin>>f[i];
	for(i=0; i<b; i++) cin>>g[i];
	s[0]=f[0];
	for(i=1; i<a; i++) s[i]=s[i-1]+f[i];
	for(i=0; i<(1<<b); i++){
		p[i].first=__builtin_popcount(i);
		for(j=0; j<b; j++){
			if(((1<<j)&i)!=0){
				jm[i]+=g[j];
			}
		}
		e=0;
		P[i]=a-1;
		for(j=0; j<a; j++){
			e+=f[j];
			if(e>jm[i]){
				P[i]=j-1;
				break;
			}
		}
		p[i].second=i;
	}
	sort(p,p+(1<<b));
	dp[0]=1;
	P[0]=-1;
	for(i=1; i<(1<<b); i++){
		for(j=0; j<b; j++){
			if(((1<<j)&p[i].second)!=0&&dp[p[i].second-(1<<j)]==1){
				if(P[p[i].second-(1<<j)]==P[p[i].second]){
					dp[p[i].second]=1;
				}else{
					if(jm[p[i].second]==s[P[p[i].second]]&&P[p[i].second-(1<<j)]+1==P[p[i].second]) dp[p[i].second]=1;
				}
			}
		}
	}
//	cout<<dp[(1<<0)]<<endl;
	e=0;
	for(i=0; i<b; i++){
		e+=g[i];
	}
	if(e<s[a-1]){
		cout<<"NO";
	}else{
		if(dp[(1<<b)-1]==1){
			cout<<"YES";
		}else{
			cout<<"NO";
		}
	}
	return 0;
}

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