제출 #1001432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001432		vjudge1	은행 (IZhO14_bank)	C++17	71 / 100	1026 ms	27216 KiB

bank

#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define x first
#define y second
#define bit(i,j) ((j >> i) & 1)
using namespace std;

const long long inf = 1e9+1;
const int mod = 1e9+7;
const int MAXN = 2e5+100;

bool dp[25][(1<<20)+2]; 
int cnt[(1 << 20)+2];
int32_t main(){
  	//freopen("A.inp", "r", stdin);
	//freopen("A.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n , m; cin >> n >> m;
	vector<int> pre(n+1) , a(n+1) , b(m+1);
	for(int i = 1; i <= n ; i ++) cin >> a[i] , pre[i] = pre[i-1] + a[i];
	for(int i = 1; i <= m ; i ++) cin >> b[i];
	
	for(int msk = 1 ; msk < (1 << m) ; msk++){
		for(int i = 0 ; i < m ; i++) if(bit(i , msk)) cnt[msk] += b[i+1];
	}
	dp[0][0] = 1;
	for(int i = 1 ; i <= n ; i++){
		for(int msk = 1 ; msk < (1 << m) ; msk++){
			if(cnt[msk] != pre[i]) continue;
			for(int s = msk ; ; s = (s-1) & msk){
				if(cnt[s] == a[i] && dp[i-1][s^msk]) {dp[i][msk] = 1; break;}
				if(!s) break;
			}
		}
	}
	for(int msk = 1 ; msk < (1 << m) ; msk++){
		if(dp[n][msk]){
			cout << "YES\n"; return 0;
		}
	}
	cout << "NO\n";

	return 0;
}

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