Subtask 1 $(N \leq 2)$:

The $N=1$ case is trivial. For $N=2$, there are 3 possibilities: only purchase the first deal, only purchase the second deal, purchase 1 of the first deal and the remaining with the second deal. We don't need to check taking an intermediate number of deals because that will always be no better than taking the cheaper deal more number of times. Therefore, we simply need to find the minimum of these 3 cases.

C++ implementation:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
void solve()
{
    int N, K, Q;
    scanf("%d %d", &N, &Q);
 
    int price[N];
    scanf("%d", &price[0]);
    for (int idx = 1; idx < N; ++idx)
    {
        scanf("%d", &price[idx]);
    }
 
    for (int idx = 0; idx < Q; ++idx)
    {
        int x;
        scanf("%d", &x);
 
        long long cost = x * (long long)(price[0]);
        if (N > 1)
        {
            cost = min(cost, (x+1)/2 * (long long)(price[1]));
            cost = min(cost, x/2 * (long long)(price[1]) + price[0]);
        }
 
        printf("%lld\n", cost);
    }
}
 
int main()
{
    solve();
 
    return 0;
}

Subtask 2 $(N \leq 10)$:

For the $i$'th deal that Farmer John offers, we can either it 0 times, take it $\lfloor \frac{x}{2^{i-1}} \rfloor$ times, or take it $\lceil \frac{x}{2^{i-1}} \rceil$ times. Once again, we don't need to check for an intermediate number of deals because that will always be no better than taking it fewer or more times.

We can use recursion to solve this. We always keep track of the minimum cost found so far. For the $i$'th deal, if we decide to take it $\lceil \frac{x}{2^{i-1}} \rceil$ number of times, then we have enough buckets of milk, so we can update the minimum cost so far if necessary and then terminate that branch. Otherwise, we recursively try another deal.

Note that we only care about the first 31 deals because $x \leq 10^9$ and $2^{30}>10^9$.

C++ implementation:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
long long minCost;
int price[100000];
 
void findMin(int curIdx, int x, long long curCost)
{
    if (x == 0)
        return;
 
    int curBuckets = 1<<curIdx;
    long long countFloor = x / curBuckets;
    long long countCeil = (x + curBuckets - 1) / curBuckets;
 
    // use all of curIdx for the remaining
    minCost = min(minCost, curCost + countCeil * price[curIdx]);
 
    if (curIdx > 0)
    {
        // use none of curIdx
        findMin(curIdx - 1, x, curCost);

        // use countFloor of curIdx
        findMin(curIdx - 1, x - countFloor*curBuckets, curCost + countFloor*price[curIdx]);
    }
}
 
void solve()
{
    int N, K, Q;
    scanf("%d %d", &N, &Q);
 
    scanf("%d", &price[0]);
    for (int idx = 1; idx < N; ++idx)
    {
        scanf("%d", &price[idx]);
    }
 
    for (int idx = 0; idx < Q; ++idx)
    {
        int x;
        scanf("%d", &x);
 
        minCost = 1e18;
        findMin(min(30, N-1), x, 0);
        printf("%lld\n", minCost);
    }
}
 
int main()
{
    solve();
 
    return 0;
}

Full Credit:

Because the size of each deal is a power of 2, we can always replicate the number of buckets of a larger deal by taking a smaller deal an appropriate number of times. We can iterate through the deals from small to large and effectively keep the lowest per bucket cost of milk so far. If Farmer John offers a larger deal at a higher per bucket cost than the lowest per bucket cost so far, we can replace the larger deal with an appropriate number of a smaller deal to get the same number of buckets for a cheaper price.

After replacing the more expensive larger deals, the per bucket cost of milk can only go down as the deal size goes up. Therefore, it is always good to take as many of the largest deals as possible, as long as we do not go over the requested $x$ buckets.

So we iterate backwards from the largest deals (up to 31) down and take each deal as many time as possible without going over $x$. While processing each deal, we also check taking that deal an extra time to see if it's actually cheaper to buy more than $x$ buckets. We always keep track of the minimum cost found so far and after processing all the deals, we would have found the overall minimum cost.

C++ implementation:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>
#include <algorithm>
using namespace std;

void solve()
{
    int N, K, Q;
    scanf("%d %d", &N, &Q);
 
    int price[N];
    scanf("%d", &price[0]);
    for (int idx = 1; idx < N; ++idx)
    {
        scanf("%d", &price[idx]);
        price[idx] = min(price[idx], 2 * price[idx-1]);
    }
 
    for (int idx = 0; idx < Q; ++idx)
    {
        int x;
        scanf("%d", &x);
 
        long long minCost = 1e18;
        long long curCost = 0;
        for (int jdx = min(30, N-1); jdx >= 0; --jdx)
        {
            int curBuckets = 1<<jdx;
            long long count = x / curBuckets;
 
            x -= count*curBuckets;
            curCost += count*price[jdx];
 
            if (x == 0)
                minCost = min(minCost, curCost);
            else
                minCost = min(minCost, curCost + price[jdx]);
        }
 
        printf("%lld\n", minCost);
    }
}
 
int main()
{
    solve();
 
    return 0;
}