Submission #1098118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098118		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	550 ms	132960 KiB

bank

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 1e6 + 7;

using namespace std;
using namespace __gnu_pbds;

ll n, m, k, p[N], f[N], a, b, c, ans, used[21][N];
vector <ll> g[N];

void rec (ll id = 1, ll mask = 0){
	if (id == m + 1){
		ans = 1;
		return;
	}
	if (used[id][mask]){
		return;
	}
	used[id][mask] = 1;
//	cout << id << ' ';
//	for (int i = 0; i < n; i++){
//		cout << (mask & (1 << i));
//	}
//	cout << '\n';
	for (int i = 0; i < g[f[id]].size(); i++){
		if ((mask & g[f[id]][i]) == 0){
			rec (id + 1, mask | g[f[id]][i]);
		}
	}
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= m; i++){
		cin >> f[i];
	}
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	for (int i = 1; i < (1 << n); i++){
		a = 0;
		for (int y = 0; y < n; y++){
			if ((i >> y) & 1){
				a += p[y + 1]; 
			}
		}
		g[a].pb (i);
	}
	ans = 0;
	rec ();
	if (ans){
		cout << "YES";
	}
	else{
		cout << "NO";
	}
}

Compilation message (stderr)

bank.cpp: In function 'void rec(long long int, long long int)':
bank.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < g[f[id]].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~

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