Submission #912721

#	Time	Username	Problem	Language	Result	Execution time	Memory
912721		csegura	Bank (IZhO14_bank)	C++14	100 / 100	155 ms	1624 KiB

bank

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;

#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int, int>             pii;
typedef pair<long long, int>       pli;
typedef pair<pii, int>              piii;
typedef pair<long long, long long> pll;
typedef pair<pll, long long>        plll;
typedef vector<int>                vi;
typedef vector<bool>                vb;
typedef vector<vector<int>>        vvi;
typedef vector<long long>          vl;
typedef vector<vector<long long>>  vvl;
typedef vector<pii>                vpii;
typedef vector<piii>               vpiii;
typedef vector<pli>                vpli;
typedef vector<pll>                vpll;
typedef vector<plll>               vplll;
typedef vector<vector<plll>>       vvplll;
typedef vector<vector<pll>>        vvpll;
typedef vector<vector<piii>>       vvpiii;
typedef vector<vector<pii>>        vvpii;
typedef vector<vector<pli>>        vvpli;

using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define data data_
#define endl "\n"
#define isOn(S, j) (S & (1ll << (j)))
#define setBit(S, j) (S |= (1ll << (j)))
#define clearBit(S, j) (S &= ~(1ll << (j)))
#define toggleBit(S, j) (S ^= (1ll << (j)))
#define bzero(b,len) (memset((b), '\0', (len)), (void) 0)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()

int main(){
	optimizar_io;
	int n, m;
	cin >> n >> m;
	int a[n+1];
	int total = 0;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		total += a[i];
	}
	int who[total+1];
	int idx = 1;
	who[0] = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < a[i]; j++){
			who[idx++] = i;
		}
	}
	int b[m];
	for (int i = 0; i < m; i++){
		cin >> b[i];
	}
	bool dp[1<<m]; //Is it valid to use the set to pay the first people
	bzero(dp, sizeof(dp));
	dp[0] = true;
	bool found = false;
	for (int i = 1; i < (1<<m); i++){
		dp[i] = false;
		int amount = 0;
		for (int j = 0; j < m; j++){
			if (isOn(i, j)){
				amount += b[j];
			}
		}
		if (amount > total) continue;
		for (int j = 0; j < m; j++){
			if (isOn(i, j)){
				int amount2 = amount - b[j];
				int bm = i ^ (1<<j);
				if ((dp[bm]) && ((who[amount] == who[amount2]) || ((who[amount2] != who[amount2+1]) && (who[amount] == who[amount2+1])))){
					dp[i] = true;
					if (amount == total){
						found = true;
					}
				}
			}
		}
	}
	if (found){
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
	return 0;
}

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