제출 #1103082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103082		hippo123	은행 (IZhO14_bank)	C++17	100 / 100	96 ms	8700 KiB

bank

#include <bits/stdc++.h>
using namespace std;

#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second

int main(){
	//freopen("bank.in", "r", stdin);
	//freopen("bank.out", "w", stdout);
	int n, m; cin>>n>>m;
	vector<int> a(n), b(m);
	for (int i=0; i<n; i++) cin>>a[i];
	for (int i=0; i<m; i++) cin>>b[i];
	
	vector<pr> dp(1<<m); // .f number of people covered, .s: remaining bills
	dp[0]={0, 0};
	
	for (int x=0; x<(1<<m); x++){
		for (int i=0; i<m; i++){
			if(x&(1<<i)) continue;
			
			pr node; 
			if(a[dp[x].f]==dp[x].s+b[i]) node={dp[x].f+1, 0};
			else {
				node={dp[x].f, dp[x].s+b[i]};
			}
			
			dp[x|(1<<i)]=max(dp[x|(1<<i)], node);
		}
	}
	if(dp[(1<<m)-1].f==n) cout<<"YES"<<endl;
	else cout<<"NO";

}

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