#include <bits/stdc++.h>
#include <ranges>
using namespace std;
#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) 42
#endif
namespace utils {
template <typename T>
bool chMax(T& target, const T& value) {
if (value > target) {
target = value;
return true;
}
return false;
}
template <typename T>
bool chMin(T& target, const T& value) {
if (value < target) {
target = value;
return true;
}
return false;
}
} // namespace utils
using namespace utils;
using ll = long long;
using ld = long double;
using mp = vector<vector<int>>;
const char el = '\n';
// Helper function to find the index of the single set bit.
// GCC and Clang provide a fast intrinsic for this.
int get_bit_index(int n) {
#ifdef __GNUC__
return __builtin_ctz(n); // Count Trailing Zeros
#else
if (n == 0) return 0;
int index = 0;
while ((n & 1) == 0) {
n >>= 1;
index++;
}
return index;
#endif
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
int N = P.size();
if (N == 0) {
return {};
}
int num_masks = 1 << N;
// dp[mask] = max tokens after buying coupons in the set 'mask'
std::vector<long long> dp(num_masks, -1);
// parent[mask] = the mask we came from to optimally reach 'mask'
std::vector<int> parent(num_masks, 0);
// Base case: 0 coupons bought, we have A tokens
dp[0] = A;
// Fill the DP table
for (int mask = 0; mask < num_masks; ++mask) {
// If this state is unreachable, we can't buy more from here
if (dp[mask] == -1) {
continue;
}
// Try to buy each coupon 'i' that is NOT in the current mask
for (int i = 0; i < N; ++i) {
// Check if i-th bit is NOT set in the mask
if (!((mask >> i) & 1)) {
// Check if we can afford coupon 'i'
if (dp[mask] >= P[i]) {
long long new_tokens = (dp[mask] - P[i]) * T[i];
int next_mask = mask | (1 << i);
// If this path is better, update dp and store the parent
if (new_tokens > dp[next_mask]) {
dp[next_mask] = new_tokens;
parent[next_mask] = mask;
}
}
}
}
}
// Find the best reachable final state (mask)
int max_coupons_count = 0;
int best_final_mask = 0;
long long max_tokens_for_best_path = -1;
for (int mask = 0; mask < num_masks; ++mask) {
if (dp[mask] != -1) {
// Get number of coupons for this mask
int current_coupons = __builtin_popcount(mask);
// If we found a path with more coupons, it's the new best
if (current_coupons > max_coupons_count) {
max_coupons_count = current_coupons;
best_final_mask = mask;
max_tokens_for_best_path = dp[mask];
}
// Tie-breaking: if coupon count is the same, prefer more tokens
else if (current_coupons == max_coupons_count) {
if (dp[mask] > max_tokens_for_best_path) {
best_final_mask = mask;
max_tokens_for_best_path = dp[mask];
}
}
}
}
// If we couldn't afford any coupons
if (max_coupons_count == 0) {
return {};
}
// Reconstruct the path by backtracking from the best final mask
std::vector<int> optimal_order;
int current_mask = best_final_mask;
while (current_mask != 0) {
int prev_mask = parent[current_mask];
// The difference in masks gives us the last coupon bought
int coupon_mask = current_mask ^ prev_mask;
int coupon_index = get_bit_index(coupon_mask);
optimal_order.push_back(coupon_index);
// Move to the previous state
current_mask = prev_mask;
}
// The path was reconstructed backwards, so reverse it
std::reverse(optimal_order.begin(), optimal_order.end());
return optimal_order;
}
