Submission #554996

#	Time	Username	Problem	Language	Result	Execution time	Memory
554996		Pulgster	Bank (IZhO14_bank)	C++17	52 / 100	1087 ms	12660 KiB

bank

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
typedef long long ll;
using namespace std;
#define pb push_back
#define imie(...) " [" << #__VA_ARGS__ << ": " << (__VA_ARGS__) << "] "
#define read(x) for(auto &i:(x))cin>>i;
const int maxn = 21;
const int mod = 1e9+7;
const ll INF64 = 1e18;
const int INF = 1e9;

// int adj[26][26];
int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	vector<int> a(n);
	vector<int> b(m);
	read(a);
	vector<vector<int>> vals(1001);
	for(int i=0;i<n;i++){
		vals[a[i]].pb(i);
	}
	read(b);
	vector<vector<int>> which(n);
	for(int i=0;i<1<<m;i++){
		int sum = 0;
		for(int k=0;k<m;k++){
			if(((1<<k)&i)>0){
				sum += b[k];
			}
		}
		if(sum <= 1000){
			for(int k : vals[sum]){
				which[k].pb(i);
			}
		}
	}
	vector<vector<int>> can(n+1, vector<int>(1<<m));
	can[0][0] = 1;
	for(int i=0;i<n;i++){
		for(int j=0;j<1<<m;j++){
			for(int k : which[i]){
				if((k & j) == 0){
					can[i+1][j|k] |= can[i][j]; 
				}
			}
		}
	}
	for(int i : can[n]){
		if(i == 1){
			cout << "YES\n";
			return 0;
		}
	}
	cout << "NO\n";
	return 0;
}	

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