제출 #731013

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

bank

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int main(){
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("shuffle.in","r",stdin);
    // freopen("shuffle.out","w",stdout);

	int n, m; cin >> n >> m;

	vector<int> pes(n);
	for(int i=0;i<n;i++) cin >> pes[i];
	vector<int> arr(m);
	for(int i=0;i<m;i++) cin >> arr[i];
	pes.pb(INF);

	vector<int> mx_qnt((1<<m)), sum((1<<m));
	mx_qnt[0]=sum[0]=0;

	for(int i=1;i<(1<<m);i++){
		mx_qnt[i]=-1;

		for(int j=0;(1<<j)<=i;j++){
			if(!(i&(1<<j))) continue;

			int qnt=mx_qnt[i-(1<<j)], val=sum[i-(1<<j)]+arr[j];
			if(val==pes[qnt]) qnt++, val=0;

			if(qnt>mx_qnt[i]){
				mx_qnt[i]=qnt;
				sum[i]=val;
			}
		}
	}

	if(mx_qnt[(1<<m)-1]==n) cout << "YES\n";
	else cout << "NO\n";
	return 0;
}

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