Submission #1175741

---

Source Code Expand

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ldp=[[0]*k for _ in xrange(n)]
rdp=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    ldp[i][0]=True
    rdp[i][0]=True
    if a[i]<k:
        ldp[i][a[i]]=True
    if a[n-i-1]<k:
        rdp[i][a[n-1-i]]=True
for i in xrange(1,n):
    for j in xrange(k):
        if j-a[i]>=0:
            ldp[i][j]|=ldp[i-1][j-a[i]]|ldp[i-1][j]
        else:
            ldp[i][j]|=ldp[i-1][j]
        if j-a[n-1-i]>=0:
            rdp[i][j]|=rdp[i-1][j-a[n-1-i]]|rdp[i-1][j]
        else:
            rdp[i][j]|=rdp[i-1][j]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            rsum[i][j]=rdp[i][j]
        else:
            rsum[i][j]=rsum[i][j-1]+rdp[i][j]
cnt=0
for i in xrange(n):
    if k-a[i]<=0:
        cnt+=1
        continue
    for j in xrange(k):
        if i==0:
            left=0
        elif i==n-1:
            if ldp[i-1][j] and a[i]+j>=k:
                cnt+=1
                break
            continue
        else:
            if ldp[i-1][j]:
                left=j
            else:
                continue
        if k-a[i]-left<=0:
            cnt+=1
            break
        if rsum[n-2-i][k-1-left]-rsum[n-2-i][k-a[i]-left-1]:
            cnt+=1
            break
print n-cnt

Submission Info

Judge Result