Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max([i, c0, c1, c2])
    return dp[n]


print(count(count(N, A, B), B, A))


Fixed submission:
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))

Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]

Q1 = [[1, 1]]
Q2 = [[1, 1]]
for i in range(3):
    if A[i] < B[i]:
        Q1 += [[A[i], B[i]]]
    elif A[i] > B[i]:
        Q2 += [[A[i], B[i]]]
dp1 = collections.defaultdict(lambda: -float('inf'))
dp1[0] = 0
for i in range(N + 1):
    for xs in Q1:
        dp1[i] = max([dp1[i], dp1[i - xs[0]] + xs[1]])
dp2 = collections.defaultdict(lambda: -float('inf'))
dp2[0] = 0
M = dp1[N]
for i in range(M + 1):
    for xs in Q2:
        dp2[i] = max([dp2[i], dp2[i - xs[1]] + xs[0]])
print(dp2[M])


Fixed submission:
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))
Buggy python submission (verdict: Time Limit Exceeded):
L = [int(_) for _ in input()[::-1]]
mod = 10**9 + 7
j = 0
ans = 0
for i in range(len(L) - 1, -1, -1):
    if L[i]:
        ans += 3**i * 2**j
        ans %= mod
        j += 1
ans += 2**j
ans %= mod
print(ans)


Fixed submission:
L = [int(_) for _ in input()[::-1]]
mod = 10**9 + 7
j = 0
ans = 0
for i in range(len(L) - 1, -1, -1):
    if L[i]:
        ans += pow(3, i, mod) * pow(2, j, mod)
        ans %= mod
        j += 1
ans += pow(2, j, mod)
ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(min([N + 1, K + 1])):
    for ir in range(min([N + 1 - il, K + 1 - il])):
        for dl in range(il + 1):
            for dr in range(ir + 1):
                if il + ir + dl + dr > K:
                    continue
                HL = V[:il]
                HR = V[N - ir:N]
                heapq.heapify(HL)
                heapq.heapify(HR)
                value = 0
                for _ in range(dl):
                    v = heapq.heappop(HL)
                    if v >= 0:
                        value += v
                        break
                value += sum(HL)
                for _ in range(dr):
                    v = heapq.heappop(HR)
                    if v >= 0:
                        value += v
                        break
                value += sum(HR)
                ans = max([ans, value])
print(ans)


Fixed submission:
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(K + 1):
    for ir in range(K + 1 - il):
        if il + ir > min([N, K]):
            continue
        H = V[:il] + V[N - ir:N]
        heapq.heapify(H)
        now = 0
        for d in range(1, il + ir):
            if il + ir + d > K:
                break
            v = heapq.heappop(H)
            if v >= 0:
                now += v
                break
        now += sum(H)
        ans = max([ans, now])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(min([N + 1, K + 1])):
    for ir in range(min([N + 1 - il, K + 1 - il])):
        for dl in range(il + 1):
            for dr in range(ir + 1):
                if il + ir + dl + dr > K:
                    continue
                HL = V[:il]
                HR = V[N - ir:N]
                heapq.heapify(HL)
                heapq.heapify(HR)
                value = 0
                for _ in range(dl):
                    v = heapq.heappop(HL)
                    if v >= 0:
                        value += v
                        break
                value += sum(HL)
                for _ in range(dr):
                    v = heapq.heappop(HR)
                    if v >= 0:
                        value += v
                        break
                value += sum(HR)
                ans = max([ans, value])
print(ans)


Fixed submission:
import heapq
N, K = [int(_) for _ in input().split()]
V = [int(_) for _ in input().split()]
ans = 0
for il in range(K + 1):
    for ir in range(K + 1 - il):
        if il + ir > min([N, K]):
            continue
        H = V[:il] + V[N - ir:N]
        heapq.heapify(H)
        now = 0
        for d in range(1, il + ir):
            if il + ir + d > K:
                break
            v = heapq.heappop(H)
            if v >= 0:
                now += v
                break
        now += sum(H)
        ans = max([ans, now])
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))


Fixed submission:
import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))

Buggy python submission (verdict: Runtime Error):
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
for i in range(1, N + 1):
    find(i)
print(len(set(UF[1:])))


Fixed submission:
import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))

Buggy python submission (verdict: Runtime Error):
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x - 1, y - 1)
for i in range(N):
    find(i)
print(len(set(UF)))


Fixed submission:
import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))
Buggy python submission (verdict: Runtime Error):
import math
ABCDE = [int(input()) for _ in range(5)]
print(
    sum([10 * math.ceil(_ / 10)
         for _ in ABCDE]) + min([_ % 10 for _ in ABCDE if _ % 10]) - 10)


Fixed submission:
import math
ABCDE = [int(input()) for _ in range(5)]
print(
    sum([10 * math.ceil(_ / 10)
         for _ in ABCDE]) + min([10] + [_ % 10 for _ in ABCDE if _ % 10]) - 10)
Buggy python submission (verdict: Runtime Error):
import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = 10**10
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(N)]
    for i in range(N):
        A[K[i]] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (N - len(A[0]) - 3)
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)


Fixed submission:
import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = 10**10
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(4)]
    for i in range(N):
        A[K[i]] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (N - len(A[0]) - 3)
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = float('inf')
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(N)]
    for i in range(N):
        k = K[i]
        A[k] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (max(len(A[1]) - 1, 0) + max(len(A[2]) - 1, 0) + max(
            len(A[3]) - 1, 0))
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)


Fixed submission:
import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = 10**10
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(4)]
    for i in range(N):
        A[K[i]] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (N - len(A[0]) - 3)
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
import collections
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
countm = len(m_n)
dp = collections.defaultdict(lambda: -float('inf'))
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = max(dp[i - m] + 1 for m, n in m_n.items())
ans = ''
ms = sorted(m_n.keys(), key=lambda _: m_n[_], reverse=True)
d = dp[N]
while N:
    for m in ms:
        if dp[N - m] == dp[N] - 1:
            N -= m
            ans += f'{m_n[m]}'
            break
print(ans)


Fixed submission:
import collections
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
dp = collections.defaultdict(lambda: -float('inf'))
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = max(dp[i - m] + 1 for m, n in m_n.items())
ans = ''
ms = sorted(m_n.keys(), key=lambda _: m_n[_], reverse=True)
d = dp[N]
while N:
    for m in ms:
        if dp[N - m] == dp[N] - 1:
            N -= m
            ans += str(m_n[m])
            break
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
count = [0] * 39
for a in A:
    for i in range(39):
        if a >> i & 1:
            count[i] += 1
if K:
    ans = sum(count[_] * 2**_ for _ in range(int(math.log2(K)) + 1, 39))
else:
    ans = sum(A)
while K:
    b = int(math.log2(K))
    if count[b] * 2 > N:
        #0をたてる
        ans += count[b] * 2**b
        K = 2**b - 1
    else:
        #1を立てる
        ans += (N - count[b]) * 2**b
        if K - 2**b:
            ans += sum(count[_] * 2**_
                       for _ in range(1 + int(math.log2(K - 2**b)), b))
        else:
            ans += sum(count[_] * 2**_ for _ in range(b))
        K -= 2**b
print(ans)


Fixed submission:
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
count = [0] * 40
if K == 0:
    print(sum(A))
    exit()
for a in A:
    for i in range(40):
        if a >> i & 1:
            count[i] += 1
ans = sum(count[_] * 2**_ for _ in range(int(math.log2(K)) + 1, 40))
while K:
    b = int(math.log2(K))
    if count[b] * 2 > N:
        #0をたてる
        ans += count[b] * 2**b
        K = 2**b - 1
    else:
        #1を立てる
        ans += (N - count[b]) * 2**b
        if K - 2**b:
            ans += sum(count[_] * 2**_
                       for _ in range(1 + int(math.log2(K - 2**b)), b))
        else:
            ans += sum(count[_] * 2**_ for _ in range(b))
        K -= 2**b
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
count = [0] * 39
for a in A:
    for i in range(40):
        if a >> i & 1:
            count[i] += 1
if K:
    ans = sum(count[_] * 2**_ for _ in range(int(math.log2(K)) + 1, 39))
else:
    ans = sum(A)
while K:
    b = int(math.log2(K))
    if count[b] * 2 > N:
        #0をたてる
        ans += count[b] * 2**b
        K = 2**b - 1
    else:
        #1を立てる
        ans += (N - count[b]) * 2**b
        if K - 2**b:
            ans += sum(count[_] * 2**_
                       for _ in range(1 + int(math.log2(K - 2**b)), b))
        else:
            ans += sum(count[_] * 2**_ for _ in range(b))
        K -= 2**b
print(ans)


Fixed submission:
import math
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
count = [0] * 40
if K == 0:
    print(sum(A))
    exit()
for a in A:
    for i in range(40):
        if a >> i & 1:
            count[i] += 1
ans = sum(count[_] * 2**_ for _ in range(int(math.log2(K)) + 1, 40))
while K:
    b = int(math.log2(K))
    if count[b] * 2 > N:
        #0をたてる
        ans += count[b] * 2**b
        K = 2**b - 1
    else:
        #1を立てる
        ans += (N - count[b]) * 2**b
        if K - 2**b:
            ans += sum(count[_] * 2**_
                       for _ in range(1 + int(math.log2(K - 2**b)), b))
        else:
            ans += sum(count[_] * 2**_ for _ in range(b))
        K -= 2**b
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])


Fixed submission:
N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(_) for _ in input().split()]
WV = sorted([[int(_) for _ in input().split()] for _ in range(N)],
            reverse=True)
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))


Fixed submission:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        dp[k + v] = min(dp_o.get(k + v, float('inf')), dp_o[k] + w)
print(max([k for k, v in dp.items() if v <= W]))


Fixed submission:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        dp[k + v] = min(dp_o.get(k + v, float('inf')), dp_o[k] + w)
print(max([k for k, v in dp.items() if v <= W]))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        if k + w <= W:
            dp[k + w] = max(dp_o.get(k + w, 0), dp_o[k] + v)
print(max([v for k, v in dp.items()]))


Fixed submission:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    dp_o = dp.copy()
    for k in dp_o:
        dp[k + v] = min(dp_o.get(k + v, float('inf')), dp_o[k] + w)
print(max([k for k, v in dp.items() if v <= W]))
Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N = I[0]
W, S, V = I[1::3], I[2::3], I[3::3]
dp = [-float('inf')] * (2 * 10**4 + 5)
dp[0] = 0
#dp[重さの総和]=その重さの総和になる最大価値
for s, w, v in sorted(zip(S, W, V), key=lambda swv: swv[0] + swv[1]):
    for wbefore in range(s, -1, -1):
        dp[wbefore + w] = max(dp[wbefore + w], dp[wbefore] + v)
print(max(dp))


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N = I[0]
W, S, V = I[1::3], I[2::3], I[3::3]
dp = [-float('inf')] * (2 * 10**4 + 5)
dp[0] = 0
#dp[重さの総和]=その重さの総和になる最大価値
for s, w, v in sorted(zip(S, W, V), key=lambda swv: swv[0] + swv[1]):
    for wbefore in range(s, -1, -1):
        dp[wbefore + w] = max(dp[wbefore + w], dp[wbefore] + v)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)


Fixed submission:
N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+1)
M = [0] * (N+1)
C = []
DM = [0] * (N+1)
DMC = [0] * (N+1)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        if c > 1:
            ans += DM[c-1]
            if c-k+1 > 0:
                ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)


Fixed submission:
N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)
Buggy python submission (verdict: Runtime Error):
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
for j in range(1, H + 1):
    dp.append([0] * W)
    for i in range(W):
        if i == 0:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
        elif i == W - 1:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
        else:
            dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
print(dp[H][K - 1])

Fixed submission:
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
if W == 1:
    print(1)
else:
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
    print(dp[H][K - 1])