Explanation

A crucial observation is that if we can make a number $x$, we can make any number $x + k\cdot a_0$, where k is a non-negative integer. We may be tempted to rewrite this as so: if we can make $x$, we can make all $y \equiv x \mod a_0$. If this is indeed the case, we can run a simple 0/1 DP to figure out what mods we can assemble, and to answer a query $b_i$, we can simply output $\texttt{dp}[b_i \mod a_0]$. However, this solution has a flaw; try to think about why before moving on!

The issue occurs when $x > a_0$. For example, if $n = 2$ and $a = \{3, 5\}$, we can construct 8, but we cannot construct 2, even though $2 \equiv 8 \mod a_0$. Fortunately, this only requires a minor fix for our DP. Try to think of it yourself, but feel free to consult the below implementation if you get stuck!

Implementation

Time Complexity: $\mathcal{O}(NA)$

The time limit is quite tight for this problem. With $n \leq 5000$ and $a_i \leq 50000$, we end up getting around $2.5\text{e}8$ operations. Here are a few optimizations I had to use:

• I use a $\texttt{vis}$ array in my implementation, and clearing it on every iteration turned out to be too slow. So instead of simply storing true/false for whether an element is visisted, I stored how many times that element had been visited across all iterations instead, taking advantage of the fact that in each iteration, all elements will be visited exactly once, thus implying that after iteration $i$, each element should have been visited a total of $i$ times. Another alternative is simply inverting $\texttt{vis}$ on each subsequent iteration: i.e. on iteration 1, false = not visited, true = visisted; but on iteration 2, false = visited, true = not visited; etc.
• Theoretically, all the $a_0$'s in the above editorial can be replaced with an arbitrary $a_i$; in fact, the condition that $a$ is sorted doesn't even matter. However, we choose it simply for being the smallest value, which marginally boosts execution time; using $a_1$ instead actually causes TLE for the following code.

While reading the following code, it may be helpful to consider that our DP is equivalent to running a shortest-path algorithm on a graph where each node $i \in [0, a_0)$ has $n$ outgoing, weighted edges to $(i + a_j) \text{ \% }a_0$ with weight $a_j$, for each $j \in [0, n).$

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 5000;
const int K = 50000;
const int INF = 1e9;

int a[N], d[K], vis[K];  // arrays and fast IO are needed for the time limit

int main() {