Submission #1354282

---

Source Code Expand

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())

dpl = [[0] * (k + 1) for _ in xrange(n)]
dpr = [[0] * (k + 1) for _ in xrange(n)]
for i in xrange(n):
    dpl[i][0] = 1
    dpr[i][0] = 1
dpl[0][min(k, a[0])] = 1
dpr[n - 1][min(k, a[n - 1])] = 1

for i in xrange(1, n):
    if a[i] > k:
        dpl[i][k] = 1
    for j in xrange(k + 1):
        if j - a[i] < 0:
            dpl[i][j] = min(1, dpl[i][j] + dpl[i - 1][j])
        else:
            dpl[i][j] = min(1, dpl[i - 1][j] + dpl[i - 1][j - a[i]])
for i in xrange(n):
    for j in xrange(k):
        dpl[i][j + 1] += dpl[i][j]

for i in xrange(n - 2, -1, -1):
    if a[i] > k:
        dpr[i][k] = 1
    for j in xrange(k + 1):
        if j - a[i] < 0:
            dpr[i][j] = min(1, dpr[i][j] + dpr[i + 1][j])
        else:
            dpr[i][j] = min(1, dpr[i + 1][j] + dpr[i + 1][j - a[i]])
for i in xrange(n - 1, -1, -1):
    for j in xrange(k):
        dpr[i][j + 1] += dpr[i][j]

ans = 0
for i in xrange(1, n - 1):
    ok = False
    if a[i] >= k: continue
    for j in xrange(k):
        if (j != 0) and (dpl[i - 1][j]  - dpl[i - 1][j - 1] == 0): continue
        lnum = j
        if lnum + a[i] >=k:
            ok=True
            break
        if dpr[i + 1][k - lnum -1] - dpr[i + 1][k - 1 - a[i] - lnum] > 0:
            ok =True
            break
    if ok: continue
    ans += 1
if a[0] < k:
    if dpr[1][k - 1] - dpr[1][k - a[0] - 1] == 0:
        ans += 1
if a[n - 1] < k:
    if dpl[n - 2][k - 1] - dpl[n - 2][k - a[n - 1] - 1] == 0:
        ans += 1
print ans

Submission Info

Judge Result