PythonでJOI難易度6を埋める #2

期末テストが終わりやっと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)