Official

B - Topping Editorial by en_translator Editorial for printing


It is sufficient to try all combinations of different three toppings. On implementing, note that the prices are from \(1\) to \(N\).

Sample code (Python)

N, V = map(int, input().split())
W = list(map(int, input().split()))
ans = 0
for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if i + j + k + 3 <= V and ans < W[i] + W[j] + W[k]:
        ans = W[i] + W[j] + W[k]
print(ans)

Another solution: the solution above costs \(\Theta(N^3)\) time, but solving it in \(\Theta(N^2)\) time is also possible, for example by grouping the three toppings into two and one.

Sample code (Python)

N, V = map(int, input().split())
W = list(map(int, input().split()))
A = [-1000000000] * V
ans = 0
for k in range(N):
  for v in range(V):
    if v + k + 1 <= V:
      ans = max(ans, A[v] + W[k])
  for i in range(k):
    v = i + k + 2
    if v < V:
      A[v] = max(A[v], W[i] + W[k])
print(ans)

posted:
last update: