Official
B - Topping Editorial by en_translator
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)