Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    State = [[0]*R for _ in range(C)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        State[c-1][r-1] += v

    dp = [[0]*4 for _ in range((C+1)*(R+1))]

    for r in range(R):
        for c in range(C):
            for n in range(4):
                if dp[(c+1)*(R+1)+r][n] > dp[(c+1)*(R+1)+r+1][0]:
                    dp[(c+1)*(R+1)+r+1][0] = dp[(c+1)*(R+1)+r][n]
                if dp[(c+1)*(R+1)+r][n] + State[c][r] > dp[(c+1)*(R+1)+r+1][1]:
                    dp[(c+1)*(R+1)+r+1][1] = dp[(c+1)*(R+1)+r][n] + State[c][r]
                if dp[c*(R+1)+r+1][n] > dp[(c+1)*(R+1)+r+1][n]:
                    dp[(c+1)*(R+1)+r+1][n] = dp[c*(R+1)+r+1][n]
                if n < 3 and dp[c*(R+1)+r+1][n] + State[c][r] > dp[(c+1)*(R+1)+r+1][n+1]:
                    dp[(c+1)*(R+1)+r+1][n+1] = dp[c*(R+1)+r+1][n] + State[c][r]
        
    print(max(dp[C*(R+1)+R]))

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    State = [[0]*R for _ in range(C)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        State[c-1][r-1] += v

    dp = [[0]*4 for _ in range(C+1)]

    for r in range(R):
        ndp = [[0]*4 for _ in range(C+1)]
        for c in range(C):
            ndp[c+1][0] = max(ndp[c+1][0], max(dp[c+1]))
            ndp[c+1][1] = ndp[c+1][0] + State[c][r]
            for n in range(4):
                if ndp[c][n] > ndp[c+1][n]:
                    ndp[c+1][n] = ndp[c][n]
                if n < 3 and ndp[c][n] + State[c][r] > ndp[c+1][n+1]:
                    ndp[c+1][n+1] = ndp[c][n] + State[c][r]
        dp = ndp
        
    print(max(dp[C]))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
S = input().rstrip()

num = S.count('1')

n1 = num + 1
n2 = num - 1

start1 = 0
start2 = 0
pow1 = [1]
pow2 = [1]
for i in range(N):
    s = int(S[-1-i])
    start1 = (start1 + pow1[-1] * s) % n1
    start2 = (start2 + pow2[-1] * s) % n2
    pow1.append(pow1[-1] * 2 % n1)
    pow2.append(pow2[-1] * 2 % n2)


def count(m):
    ret = 1
    while m != 0:
        k = bin(m).count("1")
        m %= k
        ret += 1
    return ret
    


ans = []
for i in range(N):
    s = int(S[i])
    if s == 0:
        l = (start1 + pow1[-i-2]) % n1
        ans.append(count(l))
    else:
        l = (start2 - pow2[-i-2]) % n2
        ans.append(count(l))

print(*ans, sep="\n")

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = input().rstrip()

num = S.count('1')

n1 = num + 1
n2 = num - 1

def count(m):
    ret = 1
    while m != 0:
        k = bin(m).count("1")
        m %= k
        ret += 1
    return ret


if n2 != 0:
    start1 = 0
    start2 = 0
    pow1 = [1]
    pow2 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        start2 = (start2 + pow2[-1] * s) % n2
        pow1.append(pow1[-1] * 2 % n1)
        pow2.append(pow2[-1] * 2 % n2)


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            l = (start2 - pow2[-i-2]) % n2
            ans.append(count(l))

    print(*ans, sep="\n")
else:
    start1 = 0
    pow1 = [1]
    for i in range(N):
        s = int(S[-1-i])
        start1 = (start1 + pow1[-1] * s) % n1
        pow1.append(pow1[-1] * 2 % n1)

        


    ans = []
    for i in range(N):
        s = int(S[i])
        if s == 0:
            l = (start1 + pow1[-i-2]) % n1
            ans.append(count(l))
        else:
            ans.append(0)

    print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))

def solve(N, A, S):
    Now = {0}
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            New = set()
            for s in Now:
                New.add(s)
                New.add(s^a)
            Now = New
        else:
            if not a in Now:
                return False
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)

Fixed submission:
import sys
input = sys.stdin.readline


Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    S = input().rstrip()
    Query.append((N, A, S))



def solve(N, A, S):
    Base = []
    for i in reversed(range(N)):
        s = S[i]
        a = A[i]
        if s == "0":
            for b in Base:
                a = min(a, a^b)
            if a:
                Base.append(a)
        else:
            for b in Base:
                a = min(a, a^b)
            if a:
                return False
                
    return True

for N, A, S in Query:
    print(0 if solve(N, A, S) else 1)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    x, y = x//g, y//g
    if x != 0 or y != 0:
        if y < 0 or (y==0 and x < 0):
            y = -y
            x = -x
        if (x, y) in As:
            As[(x, y)] += 1
        else:
            As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        if x > 0:
            ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

Fixed submission:
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    if g == 0:
        Empty += 1
        continue
    x, y = x//g, y//g
    if y < 0 or (y==0 and x < 0):
        y = -y
        x = -x
    if (x, y) in As:
        As[(x, y)] += 1
    else:
        As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1+Empty)%mod)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    x, y = x//g, y//g
    if x == 0 and y == 0:
        Empty += 1
    else:
        if y < 0 or (y==0 and x < 0):
            y = -y
        if (x, y) in As:
            As[(x, y)] += 1
        else:
            As[(x, y)] = 1

M = N - Empty
ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        if x > 0:
            ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

Fixed submission:
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    if g == 0:
        Empty += 1
        continue
    x, y = x//g, y//g
    if y < 0 or (y==0 and x < 0):
        y = -y
        x = -x
    if (x, y) in As:
        As[(x, y)] += 1
    else:
        As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1+Empty)%mod)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = max([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L2, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L2, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([0, i2, i3])+L1 - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))

Fixed submission:
import sys
input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = sum([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L3, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L3, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([L1, L2+i2, L3+i3]) - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

Num_str = list(input().rstrip())
L = len(Num_str)
Num = []

for n in reversed(Num_str):
    Num.append(int(n))

S = 0
up = False
for i, n in enumerate(Num):
    if up:
        n += 1
    if n < 5:
        S += n
        up = False
    elif n == 5:
        S += 5
        up = (i != L and Num[i+1] >= 5)
    else:
        S += 10 - n
        up = True
if up:
    S += 1
print(S)

Fixed submission:
import sys
input = sys.stdin.readline

Num_str = list(input().rstrip())
L = len(Num_str)
Num = []

for n in reversed(Num_str):
    Num.append(int(n))

S = 0
up = False
for i, n in enumerate(Num):
    if up:
        n += 1
    if n < 5:
        S += n
        up = False
    elif n == 5:
        S += 5
        up = (i != L-1 and Num[i+1] >= 5)
    else:
        S += 10 - n
        up = True
if up:
    S += 1
print(S)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

Num_str = list(input().rstrip())
L = len(Num_str)
Num = []

for n in reversed(Num_str):
    Num.append(int(n))

S = 0
up = False
for i, n in enumerate(Num):
    if up:
        n += 1
    if n < 5:
        S += n
        up = False
    elif n == 5:
        S += 5
        up = i != L and Num[i+1] >= 5
    else:
        S += 10 - n
        up = True
if up:
    S += 1
print(S)

Fixed submission:
import sys
input = sys.stdin.readline

Num_str = list(input().rstrip())
L = len(Num_str)
Num = []

for n in reversed(Num_str):
    Num.append(int(n))

S = 0
up = False
for i, n in enumerate(Num):
    if up:
        n += 1
    if n < 5:
        S += n
        up = False
    elif n == 5:
        S += 5
        up = (i != L-1 and Num[i+1] >= 5)
    else:
        S += 10 - n
        up = True
if up:
    S += 1
print(S)
Buggy python submission (verdict: Runtime Error):
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**6+6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for c in range(c1, c2+1):
    ans += cmb(c+r2+1, r2) - cmb(c+r1, r1-1)
    ans %= mod
print(ans)

Fixed submission:
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 3*10**6+6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

r1, c1, r2, c2 = map(int, input().split())

ans = 0
for c in range(c1, c2+1):
    ans += cmb(c+r2+1, r2) - cmb(c+r1, r1-1)
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
mod = 10**9+7

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))

dic = {}
for a in A:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

lcm = 1
for num, count in dic.items():
    lcm *= pow(num, count, mod)

ans = 0
for a in A:
    ans += mod_inv(a)*lcm
    ans %= mod

print(ans)

Fixed submission:
import math
mod = 10**9+7

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))

dic = {}
for a in A:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

lcm = 1
for num, count in dic.items():
    lcm *= pow(num, count, mod)
    lcm %= mod

ans = 0
for a in A:
    ans += mod_inv(a)*lcm
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, X, D = map(int, input().split())

C = {}
Que = {}
for l in range(N+1):
    start = l*X//D + l*(l-1)//2
    end = start + l*(N-l)
    key = l*X%D
    if key in Que:
        Que[key].append((start, end))
        C[key] += [start, end, start+1, end+1, start-1, end-1]
    else:
        Que[key] = [(start, end)]
        C[key] = [start, end, start+1, end+1, start-1, end-1]


ans = 0
for key, List in C.items():
    ind_to_co = sorted(list(set(List)))
    co_to_ind = {a:i for i, a in enumerate(ind_to_co)}

    Imos = [0]*(len(ind_to_co)+1)
    for start, end in Que[key]:
        Imos[co_to_ind[start]] += 1
        Imos[co_to_ind[end+1]] -= 1

    for i in range(len(ind_to_co)-1):
        a = ind_to_co[i]; b = ind_to_co[i+1]
        Imos[i+1] += Imos[i]
        if Imos[i+1] > 0 and Imos[i] > 0:
            ans += b-a
        elif Imos[i] > 0:
            ans += 1
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

N, X, D = map(int, input().split())

if D == 0:
    ans = N+1 if X != 0 else 1
else:
    C = {}
    Que = {}
    for l in range(N+1):
        start = l*X//D + l*(l-1)//2
        end = start + l*(N-l)
        key = l*X%D
        if key in Que:
            Que[key].append((start, end))
            C[key] += [start, end, start+1, end+1, start-1, end-1]
        else:
            Que[key] = [(start, end)]
            C[key] = [start, end, start+1, end+1, start-1, end-1]


    ans = 0
    for key, List in C.items():
        ind_to_co = sorted(list(set(List)))
        co_to_ind = {a:i for i, a in enumerate(ind_to_co)}

        Imos = [0]*(len(ind_to_co)+1)
        for start, end in Que[key]:
            Imos[co_to_ind[start]] += 1
            Imos[co_to_ind[end+1]] -= 1

        for i in range(len(ind_to_co)-1):
            a = ind_to_co[i]; b = ind_to_co[i+1]
            Imos[i+1] += Imos[i]
            if Imos[i+1] > 0 and Imos[i] > 0:
                ans += b-a
            elif Imos[i] > 0:
                ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def main():
    N, M, L = map(int, input().split())
    INF = 10**13
    dis = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        dis[a-1][b-1] = c
        dis[b-1][a-1] = c
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
    
    movable = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i != j and dis[i][j] <= L:
                movable[i].append(j)
    

    for s, t in Query:
        s, t = s-1, t-1
        q = movable[s]
        checked = [False]*N
        ok = False
        for p in q:
            if p == t:
                ok = True
            checked[p] = True
        checked[s] = True
        
        if ok:
            print(0)
            continue
        c = 0
        while q:
            c += 1
            qq = []
            for p in q:
                for np in movable[p]:
                    if np == t:
                        ok = True
                        break
                    if not checked[np]:
                        qq.append(np)
                        checked[np] = True
            if ok: break
            q = qq
        if ok:
            print(c)
        else:
            print(-1)



            



if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline


def main():
    N, M, L = map(int, input().split())
    INF = 10**13
    dis = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        dis[a-1][b-1] = c
        dis[b-1][a-1] = c
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
    
    movable = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i != j and dis[i][j] <= L:
                movable[i].append(j)
    

    for s, t in Query:
        s, t = s-1, t-1
        q = movable[s]
        checked = [False]*N
        ok = False
        for p in q:
            if p == t:
                ok = True
                break
            checked[p] = True
        checked[s] = True
        
        if ok:
            print(0)
            continue
        c = 0
        while q:
            c += 1
            qq = []
            for p in q:
                for np in movable[p]:
                    if np == t:
                        ok = True
                        break
                    if not checked[np]:
                        qq.append(np)
                        checked[np] = True
            if ok: break
            q = qq
        if ok:
            print(c)
        else:
            print(-1)



            



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())

# 最長共通接頭辞問題(Z-Algorithm)
# 文字列SとS[i:]の最長共通接頭辞を各iについて求める
# 参考：https://codeforces.com/blog/entry/3107
# 図がわかりやすい:https://snuke.hatenablog.com/entry/2014/12/03/214243


def Z_Algorithm(S):
    N = len(S)
    R = 0 # Rはi文字目まで読んだ時、接頭辞の右端のうち一番右側にくるようなもの
    L = 0 # Lはその範囲の左端
    Z = [0 for _ in range(N)] # 答えとなる最長接頭辞の長さ
    Z[0] = N

    for i in range(1, N):
        if i > R:
            # iが前のRより右側ならS[i:]とSのみで考える
            L = i
            R = i
            while (R < N and S[R-L] == S[R]):
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            k = i - L
            if Z[k] < R - i + 1:
                # はみ出さないなら前のがそのまま使える。R,Lはそのまま
                Z[i] = Z[k]
            else:
                # はみ出したら伸ばしてく
                L = i
                while (R < N and S[R-L] == S[R]):
                    R += 1
                Z[i] = R - L
                R -= 1
    return Z

ans = 0
for i in range(N):
    Z = Z_Algorithm(S[i:])
    for j, z in enumerate(Z):
        ans = max(ans, min(z, j))
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
S = list(input())

# 最長共通接頭辞問題(Z-Algorithm)
# 文字列SとS[i:]の最長共通接頭辞を各iについて求める
# 参考：https://codeforces.com/blog/entry/3107
# 図がわかりやすい:https://snuke.hatenablog.com/entry/2014/12/03/214243


def Z_Algorithm(S):
    N = len(S)
    R = 0 # Rはi文字目まで読んだ時、接頭辞の右端のうち一番右側にくるようなもの
    L = 0 # Lはその範囲の左端
    Z = [0 for _ in range(N)] # 答えとなる最長接頭辞の長さ
    Z[0] = N

    for i in range(1, N):
        if i > R:
            # iが前のRより右側ならS[i:]とSのみで考える
            L = i
            R = i
            while (R < N and S[R-L] == S[R]):
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            k = i - L
            if Z[k] < R - i + 1:
                # はみ出さないなら前のがそのまま使える。R,Lはそのまま
                Z[i] = Z[k]
            else:
                # はみ出したら伸ばしてく
                L = i
                while (R < N and S[R-L] == S[R]):
                    R += 1
                Z[i] = R - L
                R -= 1
    return Z


def main():
    ans = 0
    for i in range(N):
        Z = Z_Algorithm(S[i:])
        for j, z in enumerate(Z):
            ans = max(ans, min(z, j))
    print(ans)


if __name__ == "__main__":
    main()