Submission #739033

#	Time	Username	Problem	Language	Result	Execution time	Memory
739033		AverageAmogusEnjoyer	Bank (IZhO14_bank)	C++17	100 / 100	110 ms	8572 KiB

bank

/*
ID: dalpone1
TASK: bank 
LANG: C++
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end() 
#define pb push_back
#define ll long long
#define nl '\n'
const int N = 20;
int dp[1 << N][2], n, m;
// dp[S][0] = max pref of people I can serve with bitmask S, dp[S][1] = remaining money
// dp[S][0] = for every i in S, if money[i] + dp[S^i][1] == needed[max(dp[S^(i)][0] + 1], dp[S][0] = maxself(dp[S^i][0] + 1), dp[S][1] = 0
int main() {
	// ifstream cin(".in");
	// ofstream cout(".out");
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<int> A(n), B(m);
	for (auto &a: A)
		cin >> a;
	for (auto &b: B)
		cin >> b;
	int sz = 1 << m;
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < m; j++) {
			if ((i & (1 << j)) == 0) continue;
			bool makes_new_one = (A[dp[i ^ (1 << j)][0]] == dp[i ^ (1 << j)][1] + B[j]);
			if (dp[i][0] <= dp[i ^ (1 << j)][0] + makes_new_one) {
				dp[i][0] = dp[i ^ (1 << j)][0] + makes_new_one;
				if (dp[i][0] == n) {
					cout << "YES";
					return 0;
				}
				if (makes_new_one)
					dp[i][1] = 0;
				else
					dp[i][1] = dp[i ^ (1 << j)][1] + B[j];
			}
		}
	}
	cout << "NO"; 
}

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