Official

B - Topping Editorial by KumaTachiRen


相異なる \(3\) 種類のトッピングを選ぶ方法を全て試せばよいです。 実装の際には価格が \(1\) から \(N\) であることに注意してください。

実装例(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)

別解:上の解法の計算量は \(\Theta(N^3)\) 時間ですが、選ぶ \(3\) 種類のトッピングを \(2\) 種類と \(1\) 種類に分けて考えるなどの方法で \(\Theta(N^2)\) 時間でも解くことができます。

実装例(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)