제출 #590796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590796		Mazaalai	은행 (IZhO14_bank)	C++17	100 / 100	115 ms	8496 KiB

bank

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using I=int;
bool done;
I main(){
	I n,m,i,j;cin>>n>>m;
	I a[n],b[m];
	pair<I,I>dp[1<<m];
	for(i=0;i<n;i++)cin>>a[i];
	for(i=0;i<m;i++)cin>>b[i];
	sort(a,a+n);sort(b,b+m);
	dp[0]={0,0};
	for(i=1;i<(1<<m)&&!done;i++){
		dp[i]={0,0};
		for(j=0;j<m;j++){
			if(!(i&(1<<j))||dp[i].f>dp[i^(1<<j)].f)continue;
			pair<I,I>&tmp=dp[i^(1<<j)];
			if(tmp.f>dp[i].f)dp[i]=tmp;
			if(a[tmp.f]>=b[j]+tmp.s&&dp[i].s<b[j]+tmp.s)dp[i].s=b[j]+tmp.s;
		}
		if(dp[i].s==a[dp[i].f])dp[i]={dp[i].f+1,0};
		done|=dp[i].f==n;
	}
	cout<<(done?"YES":"NO")<<"\n";
}

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