問題概要
問題ページ
-
F - Programming Contest
問題ページへ移動する
問題文
高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は \(T\) 分間で、 \(N\) 問の問題が出題されます。
高橋くんは超能力者なので、 \(i\) 番目の問題が \(A_i\) 分で解けることが分かっています。
高橋くんは \(N\) 問の中から \(0\) 問以上を、解くのにかかる時間の総和が \(T\) 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。
制約
- 入力は全て整数
- \(1 \le N \le 40\)
- \(1 \le T \le 10^9\)
- \(1 \le A_i \le 10^9\)
問題の考察
ACコード
import sys
import bisect
import itertools
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n, t = list(map(int, input().rstrip('\n').split()))
a = list(map(int, input().rstrip('\n').split()))
b = a[:len(a) // 2]
c = a[len(a) // 2:]
bc = []
cc = []
for v in itertools.product(range(2), repeat=len(b)):
total = 0
for i in range(len(b)):
total += b[i] if v[i] == 1 else 0
bc.append(total)
for v in itertools.product(range(2), repeat=len(c)):
total = 0
for i in range(len(c)):
total += c[i] if v[i] == 1 else 0
cc.append(total)
bc.sort()
cc.sort()
mx = 0
for v in bc:
pos = bisect.bisect_right(cc, t - v)
sm = v + cc[pos - 1]
sm = sm if sm <= t else 0
mx = max(mx, sm)
print(mx)
if __name__ == '__main__':
solve()