Vault
There are $2M + 1$ kinds of weights, whose mass are $-M, -M + 1, \ldots, M - 1, M$. However, you do not have an infinite number of weights. For each mass $\ell$, there are only $A_{\ell}$ such weights. You want to choose some weights such that their total mass is exactly $L$. In this case, you want to maximize the number of weights you choose.
$1 \leq M \leq 300$
$0 \leq A_{\ell} \leq 10^{12}$
$-10^{18} \leq L \leq 10^{18}$
Time limit: 4 seconds.
Editorial
Intuition tells us that if we first determine the set of weights $\mathcal S$ whose total mass is close to $L$, then we can adjust $\mathcal S$ within an acceptable time complexity.
First, add all the weights to $\mathcal S$. Then we will continuously remove the maximum weight from $\mathcal S$ until the total mass in it is less than or equal to $L$. Thus the total mass well be within $\left[L - M + 1, L\right]$. However, if the total mass of all weights is less than $L$, we will remove the minimum weight from $\mathcal S$. Since both cases are symmetric, we will focus only on the first case.
Consider the adjustment method. If the current mass of $\mathcal S$ is less than $L$, then we will inevitably either add a positive weight or remove a negative weight later. we might as well do this in advance. We will find that the total mass will still be within $\left[L - M + 1, L + M - 1\right]$.
We will observe the following fact: if the current mass of $\mathcal S$ is $W_0$, it is irrational to add and remove weights to obtain another set $\mathcal S'$ with the same total mass $W_0$. Thus, we only reach the same total mass at most once. This means we have to add or remove weights at most $O\left(M\right)$ times, implying that if the order is not taken into consideration, the total mass of $\mathcal S$ is within $\left[L - M^2, L + M^2\right]$.
Therefore, we can perform DP in $\tilde O\left(M^3\right)$.
Code
struct SNOWFLAKE {
static constexpr char __FIO__[] = "";
static constexpr char __FIN__[] = "";
static constexpr char __FOUT__[] = "";
static constexpr bool MTS = false;
static constexpr bool SPC_MTS = false;
SNOWFLAKE() {
if (strlen(__FIO__) != 0) {
freopen((std::string(__FIO__) + ".in").c_str(), "r", stdin);
freopen((std::string(__FIO__) + ".out").c_str(), "w", stdout);
} else {
if (strlen(__FIN__) != 0) freopen(__FIN__,"r",stdin);
if (strlen(__FOUT__) != 0) freopen(__FOUT__, "w",stdout);
}
std::cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
if (MTS && !SPC_MTS) std::cin >> t;
for (int i = 1; i <= t || SPC_MTS; ++i) {
if (TRANSMIGRATION(i) != 0) return;
}
}
template <typename Ty>
using vla = std::vector<Ty>;
using string = std::string;
using ll = long long int;
using ull = unsigned long long int;
using vb = vla<bool>;
using vi = vla<int>;
using vl = vla<ll>;
using vvi = vla<vi>;
using vvl = vla<vl>;
using pii = std::pair<int, int>;
using pil = std::pair<int, ll>;
using pli = std::pair<ll, int>;
using pll = std::pair<ll, ll>;
static constexpr int INF32 = 0x3ffffffe;
static constexpr ll INF64 = 0x3ffffffffffffffe;
int TRANSMIGRATION([[maybe_unused]] int TEST_NUMBER) {
int n; std::cin >> n;
ll m; std::cin >> m;
vl a(2 * n + 1);
for (ll& i : a) std::cin >> i;
vl f(2 * n * n + 1, -INF64);
ll sum = 0;
for (int i = -n; i <= n; ++i) sum += a[i + n] * i;
vl use = a;
for (int i = n; i > 0 && sum > m; --i) {
if (sum - a[i + n] * i >= m) {
sum -= a[i + n] * i;
use[i + n] = 0;
continue;
}
ll x = (sum - m - 1) / i + 1;
sum -= x * i;
use[i + n] = a[i + n] - x;
}
for (int i = -n; i < 0 && sum < m; ++i) {
if (sum - a[i + n] * i <= m) {
sum -= a[i + n] * i;
use[i + n] = 0;
continue;
}
ll x = (m - sum - 1) / (-i) + 1;
sum -= x * i;
use[i + n] = a[i + n] - x;
}
if (abs(sum - m) >= n) {
std::cout << "impossible\n";
return 0;
}
f[sum - m + n * n] = accumulate(use.begin(), use.end(), 0ll);
auto dp = [&](int w, int c, int v) {
if (w > 0) {
for (int o = 1; c > 0; o *= 2) {
o = std::min(o, c);
for (int i = n * n; i >= o * w - n * n; --i) {
f[i + n * n] = std::max(f[i + n * n], f[i + n * n - o * w] + o * v);
}
c -= o;
}
} else {
for (int o = 1; c > 0; o *= 2) {
o = std::min(o, c);
for (int i = -n * n; i <= n * n + o * w; ++i) {
f[i + n * n] = std::max(f[i + n * n], f[i + n * n - o * w] + o * v);
}
c -= o;
}
}
};
for (int i = -n; i <= n; ++i) {
if (i == 0) continue;
if (use[i + n] < a[i + n]) dp(i, std::min((ll)n, a[i + n] - use[i + n]), 1);
if (use[i + n] > 0) dp(-i, std::min((ll)n, use[i + n]), -1);
}
if (f[n * n] < 0) std::cout << "impossible\n";
else std::cout << f[n * n] << "\n";
return 0;
}
} SNOWFLAKE;