Submission #18313090

---

Source Code Expand

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def compute(A):
    N = len(A)
    dp = np.zeros(1 << N, np.int64)
    for i in range(N):
        x = A[i]
        dp[1 << i:1 << i + 1] = dp[:1 << i] + x
        dp[:1 << i + 1].sort(kind='mergesort')
    return dp

def main(T, A):
    N = len(A)
    if N == 1:
        A[0] if T > A[0] else 0
    L = compute(A[:N // 2])
    R = compute(A[N // 2:])
    L = L[L <= T]
    R = R[R <= T]
    idx = np.searchsorted(R, T - L, 'right') - 1
    return (L + R[idx]).max()

N, T = from_readline()
A = from_readline()

print(main(T, A))

Submission Info

Judge Result