Submission #18313090


Source Code Expand

Copy
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

Submission Time
Task F - Programming Contest
User maspy
Language Python (3.8.2)
Score 600
Code Size 903 Byte
Status AC
Exec Time 192 ms
Memory 60812 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All hand_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
hand_01.txt AC 118 ms 26872 KB
random_01.txt AC 112 ms 27356 KB
random_02.txt AC 112 ms 27188 KB
random_03.txt AC 111 ms 27112 KB
random_04.txt AC 113 ms 27132 KB
random_05.txt AC 113 ms 27192 KB
random_06.txt AC 115 ms 26864 KB
random_07.txt AC 112 ms 27060 KB
random_08.txt AC 114 ms 27156 KB
random_09.txt AC 114 ms 27108 KB
random_10.txt AC 114 ms 27068 KB
random_11.txt AC 118 ms 27160 KB
random_12.txt AC 115 ms 27476 KB
random_13.txt AC 118 ms 31408 KB
random_14.txt AC 114 ms 26928 KB
random_15.txt AC 115 ms 27176 KB
random_16.txt AC 113 ms 27044 KB
random_17.txt AC 113 ms 27104 KB
random_18.txt AC 111 ms 27208 KB
random_19.txt AC 114 ms 27640 KB
random_20.txt AC 121 ms 31208 KB
random_21.txt AC 113 ms 27432 KB
random_22.txt AC 118 ms 31296 KB
random_23.txt AC 143 ms 47144 KB
random_24.txt AC 146 ms 47164 KB
random_25.txt AC 146 ms 47160 KB
random_26.txt AC 187 ms 60812 KB
random_27.txt AC 192 ms 60756 KB
random_28.txt AC 145 ms 47156 KB
random_29.txt AC 145 ms 47144 KB
random_30.txt AC 144 ms 47340 KB
sample_01.txt AC 116 ms 27140 KB
sample_02.txt AC 112 ms 27368 KB
sample_03.txt AC 111 ms 27072 KB
sample_04.txt AC 112 ms 26792 KB