제출 #679306

#제출 시각아이디문제언어결과실행 시간메모리
679306RadicaI은행 (IZhO14_bank)C++17
100 / 100
420 ms21820 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,m; cin >> n>>m;
	bool dp[1<<m][n+1];
	for(int i=0; i<1<<m; i++)for(int j=0; j<=n; j++) dp[i][j]=false;
	int a[n+1];
	for(int i=0; i<n; i++) cin >> a[i+1];
	int psum[n+1];psum[0]=0; for(int i=1; i<=n; i++) psum[i] = psum[i-1]+a[i];
	int bank[m];
	for(int i=0; i<m; i++)cin >> bank[i];
	for(int i=0; i<m; i++) dp[1<<i][0]=true;
	for(int mask =1; mask<1<<m; mask++){
		dp[mask][0]=true;
		int tot=0;
		for(int i=0; i<m; i++) if(mask & (1<<i))tot+=bank[i];
		for(int i=1; i<=n; i++) if(tot==psum[i] && dp[mask][i-1])dp[mask][i] =1;
		for(int i=0; i<m; i++) if(!(mask & (1<<i))){
			for(int j=0; j<=n; j++) dp[mask^(1<<i)][j] = (dp[mask^(1<<i)][j]) || (dp[mask][j]);
		}
	}
	if(dp[(1<<m)-1][n]) cout <<"YES";
	else cout <<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...