期末テストが終わりやっとJOIできると思ったら,あと一週間しかないこの頃.
C - ダーツ
めちゃくちゃ有名?な問題.半分全探索で解けます.
from bisect import bisect_left n, m = map(int, input().split()) p = [int(input()) for _ in range(n)] one_throw = sorted(p) two_throw = [] for i in range(n): for j in range(n): two_throw.append(p[i] + p[j]) two_throw.sort() for i in range(4): if i == 0: #一回投げる index = bisect_left(one_throw, m) if index == 0: continue ans = one_throw[index - 1] if i == 1: #二回投げる index = bisect_left(two_throw, m) if index == 0: continue ans = max(two_throw[index - 1], ans) if i == 2: #三回投げる for j in range(n): w = m - one_throw[j] #許容できるスコア index = bisect_left(two_throw, w) if index == 0: continue ans = max(two_throw[index - 1] + one_throw[j], ans) if i == 3: #四回投げる for j in range(n ** 2): w = m - two_throw[j] index = bisect_left(two_throw, w) if index == 0: continue ans = max(two_throw[index - 1] + two_throw[j], ans) print(ans)