Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import math
import heapq
import numpy
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
As=LI()
As.sort()
len_As = len(As)
Acum=numpy.cumsum(As)
# print(As)
# print(Acum)

ok = 0
ng = 2*max(As)

pat = 0
sm = 0
while ng - ok > 1:
    mid_sum = (ok + ng)//2
    pat = 0
    sm = 0
    for A in As:
        A2 = mid_sum - A
        # print(A2)
        lft = bisect.bisect_left(As, A2)
        pat += len_As - lft
        sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A
    # print(pat, M, ok, ng)

    if pat < M: ng = mid_sum
    else: ok = mid_sum

pat = 0
sm = 0
for A in As:
    A2 = ok - A
    # print(A2)
    lft = bisect.bisect_left(As, A2)
    pat += len_As - lft
    sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A

# print("lo:{} hi:{} pat:{} sum:{}".format(ok, ng, pat, sm))

print(sm - (pat-M)*ok)


Fixed submission:
import sys
import math
import heapq
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
As=LI()
As.sort()
len_As = len(As)
Acum=[As[0]]
for i in range(1, len_As):
    Acum.append(Acum[i-1]+As[i])
# print(As)
# print(Acum)

ok = 0
ng = 2*max(As)+1

pat = 0
sm = 0
while ng - ok > 1:
    mid_sum = (ok + ng)//2
    pat = 0
    sm = 0
    for A in As:
        A2 = mid_sum - A
        # print(A2)
        lft = bisect.bisect_left(As, A2)
        pat += len_As - lft
        sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A
    # print(pat, M, ok, ng)

    if pat < M: ng = mid_sum
    else: ok = mid_sum

pat = 0
sm = 0
for A in As:
    A2 = ok - A
    # print(A2)
    lft = bisect.bisect_left(As, A2)
    pat += len_As - lft
    sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A

# print("lo:{} hi:{} pat:{} sum:{}".format(ok, ng, pat, sm))

print(sm - (pat-M)*ok)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST=[(-1,-1) for i in range(N+1)]
DIST[v] = (0, -1)
def dfs(root=v):
    maxdist = DIST[root][0]
    for vtx in TR[root]:
        if DIST[vtx][0] == -1:
            DIST[vtx] = (DIST[root][0] + 1, -1)
            maxdist = max(maxdist, dfs(vtx))
    DIST[root] = (DIST[root][0], maxdist)
    return maxdist

DIST2=[(-1,-1) for i in range(N+1)]
LST = 0
def dfs2(root=u):
    global LST
    maxdist = DIST2[root][0]
    for vtx in TR[root]:
        if DIST2[vtx][0] == -1 and DIST2[root][0] + 1 < DIST[vtx][0]:
            LST = max(LST, DIST[vtx][0])
            DIST2[vtx] = (DIST2[root][0] + 1, -1)
            maxdist = max(maxdist, dfs2(vtx))
    DIST2[root] = (DIST2[root][0], maxdist)
    return maxdist

dfs()
dfs2()
# print(DIST)
# print(DIST2)

print(max(0, LST-1))


Fixed submission:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST1=[-1]*(N+1)
DIST2=[-1]*(N+1)
FIFO = deque()

FIFO.append((v,0))
while FIFO:
    edge, dist = FIFO.popleft()
    DIST1[edge] = dist
    for i in TR[edge]:
        if DIST1[i] == -1:
            FIFO.append((i, dist+1))

FIFO.append((u, 0))

farest = 0
while FIFO:
    edge, dist = FIFO.popleft()
    DIST2[edge] = dist
    farest = max(farest, DIST1[edge])
    for i in TR[edge]:
        if DIST2[i] == -1 and dist+1 < DIST1[i]:
            FIFO.append((i, dist+1))

# print(DIST1)
# print(DIST2)
print(max(0, farest-1))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N,K=LI()
MP=[0] + LI()
LG = 10**15
DP=[[LG]*(N+1) for i in range(N-K+1)]
DP[0][0] = 0

for i in range(1, N+1):
    DP[1][i] = MP[i]

for i in range(1, N-K):
    for j in range(1, N+1):
        for k in range(1, j):
            DP[i+1][j] = min(DP[i+1][j], DP[i][k] + max(0, MP[j] - MP[k]))

res = 10**15
for i in range(1, N+1):
    res = min(res, DP[N-K][i])
print(res)


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N,K=LI()
MP=[0] + LI()
LG = 10**15
DP=[[LG]*(N+1) for i in range(N-K+2)]

for i in range(1, N+1):
    DP[0][i] = 0
    DP[1][i] = MP[i]

for i in range(1, N-K):
    for j in range(1, N+1):
        for k in range(1, j):
            DP[i+1][j] = min(DP[i+1][j], DP[i][k] + max(0, MP[j] - MP[k]))

res = 10**15
for i in range(1, N+1):
    res = min(res, DP[N-K][i])
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K=LI()
As=LI()
As.sort()
Fs=LI()
Fs.sort(reverse=True)

HQ=[]

for i in range(N):
    heapq.heappush(HQ, (-As[i]*Fs[i], As[i], Fs[i]))

# print(HQ)
while K:
    score,A,F=heapq.heappop(HQ)
    if HQ:
        score2,A2,F2=HQ[0]
        diff = min((score2 - score) // F + 1, K)

        heapq.heappush(HQ, (-(A-diff)*F , A-diff, F))
        K = K - diff
    else:
        print(max(A-K,0)*F)
        exit()

ans, _, _ =heapq.heappop(HQ)
print(-ans)


Fixed submission:
import sys
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,K=LI()
As=LI()
As.sort()
Fs=LI()
Fs.sort(reverse=True)

rgt = 10**12
lft = 0
while lft < rgt:
    cost = K
    half = (lft + rgt) // 2
    for i in range(N):
        if As[i]*Fs[i] > half:
            cost -= (As[i]*Fs[i] - half) // Fs[i]
            cost -= 1 if (half - As[i]*Fs[i]) % Fs[i] > 0 else 0

    if cost < 0:
        lft = half + 1
    else:
        rgt = half
    # print(lft, rgt)

print(rgt)
Buggy python submission (verdict: Runtime Error):
print(II()**3)


Fixed submission:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

print(II()**3)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y


N,Q=LI()
TR=[[] for i in range(N+1)]
TR_score = [0] * (N+1)
RES = [-1]*(N+1)

for i in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

for i in range(Q):
    p, x = LI()
    TR_score[p] += x

ST = [(1, TR_score[1])]
while ST:
    i, score = ST.pop()
    RES[i] = score
    for j in TR[i]:
        if RES[j] == -1:
            ST.append((j, score + TR_score[j]))

for value in RES[1:-1]: print(value, end=" ")
print(RES[-1])


Fixed submission:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y


N,Q=LI()
TR=[[] for i in range(N+1)]
TR_score = [0] * (N+1)
RES = [-1]*(N+1)

for i in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

for i in range(Q):
    p, x = LI()
    TR_score[p] += x

ST = [(1, TR_score[1])]
while ST:
    i, score = ST.pop()
    RES[i] = score
    for j in TR[i]:
        if RES[j] == -1:
            ST.append((j, score + TR_score[j]))

for value in RES[1:-1]: print(value, end=" ")
print(RES[-1])
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
lenS=len(S)

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)


Fixed submission:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

S=input()
T=input()
lenS=len(S)

NX=[[-1]*26 for _ in range(len(S))]

for i in range(len(S)*2-1)[::-1]:
    idx = i%lenS
    idx2 = (i+1)%lenS
    for j in range(26):
        if NX[idx2][j] != -1:
            NX[idx][j] = NX[idx2][j] + 1
    NX[idx][ord(S[idx2])%26] = 1

# for lis in NX:
#     print(lis)
# for c in S:
#     print(ord(c)%26, end=" ")
# print("")

res = 0
prev=lenS-1
for c in T:
    v = NX[prev][ord(c)%26]
    if v == -1:
        print(-1)
        exit()
    else:
        res += v
        prev = (prev + v)%lenS

print(res)
Buggy python submission (verdict: Runtime Error):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)
# DIVS.sort(reversed=True)
# print(DIVS)

DIFF=[0]*N
ACC=[0]*N

# res = 0

for x in devisor:
  b = [a[i]%x for i in range(n)]
  b.sort()
  sumb = list(accumulate(b))
  for y in range(n-1):
    bf = sumb[y]
    bl = sumb[n-1]-sumb[y]
    if bf%x == (x-(bl%x))%x:
      if k>=max(bf,(n-1-y)*x-bl):
        print(x)
        exit()
      else:
        continue

for div in sorted(DIVS, reverse=True):
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    ACC[0] = DIFF[0]
    for i in range(1,N): ACC[i] = ACC[i-1] + DIFF[i]
    # print(ACC)
    for i in range(N-1):
        left = ACC[i]
        right = (N-1-i)*div-(ACC[N-1]-ACC[i])
        if left%div == right%div:
            if max(left, right) <= K:
                # print(max(left, right))
                print(div)
                exit()


# print(DIFF)
# print(res)


Fixed submission:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,K=LI()
AS=LI()
SUMM= sum(AS)

DIVS=set()
for i in range(1,40000):
    if SUMM % i == 0:
        DIVS.add(i)
        DIVS.add(SUMM//i)
# DIVS.sort(reversed=True)
# print(DIVS)

DIFF=[0]*N
ACC=[0]*N

# res = 0

for div in sorted(DIVS, reverse=True):
    for i in range(N):
        DIFF[i] = AS[i]%div
    DIFF.sort()
    ACC[0] = DIFF[0]
    for i in range(1,N): ACC[i] = ACC[i-1] + DIFF[i]
    # print(ACC)
    for i in range(N-1):
        left = ACC[i]
        right = (N-1-i)*div-(ACC[N-1]-ACC[i])
        if left%div == right%div:
            if max(left, right) <= K:
                # print(max(left, right))
                print(div)
                exit()


# print(DIFF)
# print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

dp=np.zeros((N+1, M+1), dtype=np.int)

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)

Fixed submission:
DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

dp=[[0]*(M+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

minusinf = -10**18

N=II()
RA=LI()
RB=LI()
GAIN1=[]
GAIN2=[]
for i in range(3):
    if RA[i] < RB[i]:
        GAIN1.append((RA[i], RB[i]-RA[i]))
    if RA[i] > RB[i]:
        GAIN2.append((RB[i], RA[i]-RB[i]))

memo1 = {}
def dp1(n):
    if n == 0: return 0
    if n < 0: return minusinf
    if n in memo1:
        return memo1[n]
    sol = 0
    for cost, g in GAIN1:
        sol = max(dp1(n-cost)+g, sol)
    memo1[n] = sol
    return sol

memo2 = {}
def dp2(n):
    if n == 0: return 0
    if n < 0: return minusinf
    if n in memo2:
        return memo2[n]
    sol = 0
    for cost, g in GAIN2:
        sol = max(dp2(n-cost)+g, sol)
    memo2[n] = sol
    return sol

med = N+dp1(N)
print(med+dp2(med)) 

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())
INTMIN = -9223372036854775808

N=II()
RA=LI()
RB=LI()
GAIN1=[]
GAIN2=[]
for i in range(3):
    if RA[i] < RB[i]:
        GAIN1.append((RA[i], RB[i]-RA[i]))
    if RA[i] > RB[i]:
        GAIN2.append((RB[i], RA[i]-RB[i]))

dp1 = [0]*(N+1)
for i in range(N+1):
    for cost, gain in GAIN1:
        if (i+cost) <= N:
            dp1[i+cost] = max(dp1[i+cost],dp1[i]+gain)

M = dp1[N]+N
dp2 = [0]*(M+1)
for i in range(M+1):
    for cost, gain in GAIN2:
        if (i+cost) <= M:
            dp2[i+cost] = max(dp2[i+cost],dp2[i]+gain)

print(M+dp2[M])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
 
H,W=LI()
MP=[input() for _ in range(H)]
 
mp_wid=[[0]*W for _ in range(H)]
mp_hei=[[0]*W for _ in range(H)]
 
for i in range(H):
    cnt = 0
    for j in range(W):
        if MP[i][j] == '.':
            cnt += 1
        else:
            for k in range(cnt):
                mp_wid[i][j-k-1] = cnt
            cnt=0
    for k in range(cnt):
        mp_wid[i][-k-1] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if MP[i][j] == '.':
            cnt+=1
        else:
            for k in range(cnt):
                mp_hei[i-k-1][j] = cnt
            cnt=0
    for k in range(cnt):
        mp_hei[-k-1][j] = cnt

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, mp_hei[i][j]+mp_wid[i][j]-1)
print(res)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

H,W=LI()
MP=[input() for _ in range(H)]

mp_wid=[[0]*W for _ in range(H)]
mp_hei=[[0]*W for _ in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if MP[i][j] == '.':
            cnt += 1
        else:
            for k in range(cnt):
                mp_wid[i][j-k-1] = cnt
            cnt=0
    for k in range(cnt):
        mp_wid[i][-k-1] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if MP[i][j] == '.':
            cnt+=1
        else:
            for k in range(cnt):
                mp_hei[i-k-1][j] = cnt
            cnt=0
    for k in range(cnt):
        mp_hei[-k-1][j] = cnt

# for li in mp_wid:
#     print(li)
# print('')
# for li in mp_hei:
#     print(li)
res = 0
for i in range(H):
    for j in range(W):
        res = max(res, mp_hei[i][j]+mp_wid[i][j]-1)
print(res)
Buggy python submission (verdict: Runtime Error):

if C < D:
    if st[A:C].find('##') >= 0 or st[B:D].find('##') >= 0:
        print('No')
    else:
        print('Yes')
else:
    # Cの方がおおきいケース 入れ替わる
    if st[A:C].find('##') >= 0:
        print('No')
    else:
        fnd = st.find('...', B-1, D+1)
        if fnd >= 0:
            print('Yes')
        else:
            print('No')

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def SI(): return input()

N,A,B,C,D=LI()
st=input()

if C < D:
    if st[A:C].find('##') >= 0 or st[B:D].find('##') >= 0:
        print('No')
    else:
        print('Yes')
else:
    # Cの方がおおきいケース 入れ替わる
    if st.find('##', A-1, C) >= 0:
        print('No')
    else:
        fnd = st.find('...', B-2, D+1)
        if fnd >= 0:
            print('Yes')
        else:
            print('No')