結果

問題 No.1861 Required Number
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2022-03-04 21:34:24
言語 PyPy3
(7.3.15)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,052 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 691,044 KB
最終ジャッジ日時 2024-07-18 22:29:47
合計ジャッジ時間 27,299 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 42 TLE * 3 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

1861:

dpだよな
O(NK)

dpをする
iが必須か？
は、 i-1 と i+1 を見ればいい

"""

import sys
from sys import stdin

N,K = map(int,stdin.readline().split())

A = list(map(int,stdin.readline().split()))

dpL = [[False] * (K+1) for i in range(N+1)]
dpR = [[False] * (K+1) for i in range(N+1)]

dpL[0][0] = True

for i in range(N):

    for nk in range(K+1):

        if dpL[i][nk]:

            dpL[i+1][nk] = True

            if nk + A[i] <= K:
                dpL[i+1][nk + A[i]] = True

if dpL[-1][-1] == False:
    print (-1)
    sys.exit()

A.reverse()
dpR[0][0] = True
for i in range(N):
    for nk in range(K+1):
        if dpR[i][nk]:
            dpR[i+1][nk] = True

            if nk + A[i] <= K:
                dpR[i+1][nk + A[i]] = True

dpR.reverse()
ans = N

for v in range(1,N+1):
    #vが必要ないか？
    #dpL[v-1] と dpR[v]を確認

    flag = False
    for lk in range(K+1):
        if dpL[v-1][lk] and dpR[v][K-lk]:
            flag = True
            break

    if flag:
        ans -= 1

print (ans)
0