제출 #679306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679306		RadicaI	은행 (IZhO14_bank)	C++17	100 / 100	420 ms	21820 KiB

bank

#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";
}

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