ABC478 B - Topping
- サイト
- AtCoder
- コンテスト
- ABC478
- 問題
- B - Topping
- 難易度
- 90
番目のトッピングは価格 、嬉しさ です。価格の総和が 以下になるように相異なる 3 種類を選ぶとき、嬉しさの総和の最大値を求める問題です()。
なので、3 つの組 を全部試しても 通りで間に合います。価格の総和 が 以下のものについて、嬉しさの総和の最大値を取ります。
コードでは添字を 始まりにしているので、価格の総和は になります。
Python
from itertools import combinations
N, V = map(int, input().split())W = list(map(int, input().split()))ans = 0for i, j, k in combinations(range(N), r=3): if i + j + k + 3 > V: continue ans = max(ans, W[i] + W[j] + W[k])print(ans)Uiua
/↥▽<⊙(+2∩(≡/+⧅<3)⇡):°⊟:∩(⊜⋕⊸≠@ &sc)∩(⊜⋕⊸≠@ &sc) で 2 行を数値の配列として読み、°⊟ で 1 行目を と に分けます。⧅<3 で添字が増加する 3 つ組をすべて作り、≡/+ で各組の和を取ります。これを ∩ で添字 ⇡ と の両方に行い、添字の和(に を足したもの)が 未満、つまり価格の総和が 以下の組だけを ▽ で残して、/↥ で最大値を取っています。