結果

問題 No.2329 Nafmo、イカサマをする
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-01 16:11:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,319 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 89,828 KB
最終ジャッジ日時 2025-05-01 16:11:19
合計ジャッジ時間 4,017 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2329


def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))

    if K == 1:
        answer = 0
        for a in A:
            if a <= M:
                answer = max(answer, a)
        print(answer)
        return
    
    k1 = K // 2
    k2 = K - k1

    # k1パート
    
    def dfs(A, M, a_set, a, k1):
        if k1 == 0:
            if a <= M:
                a_set.add(a)
            return
        
        for x in A:
            dfs(A, M, a_set, a + x, k1 - 1)
        

    A = [0] + A
    a_set = set()
    dfs(A, M, a_set, 0, k1)
    b_set = set()
    dfs(A, M, b_set, 0, k2)

    b_array = list(b_set)
    b_array.sort()

    answer = 0
    for a in a_set:
        m = M - a
        if len(b_array) == 0:
            continue

        if b_array[0] > m:
            continue

        low = 0
        high = len(b_array) - 1
        while high - low > 1:
            mid  =(high + low) //2
            if b_array[mid] <= m:
                low = mid

            else:
                high = mid
        if b_array[high] <= m:
            ans = b_array[high] + a
        else:
            ans = b_array[low] + a
        
        answer = max(answer, ans)
    print(answer)
        

    




if __name__ == "__main__":
    main()
0