Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
h,w = map(int,input().split())
a = [input() for i in range(h)]

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<w and 0<=j+l<h:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True
    ans = max(ans,cnt)

print(ans)



Fixed submission:
h,w = map(int,input().split())
a = [input() for i in range(h)]

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    ans = max(ans,cnt)
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<h and 0<=j+l<w:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
a = [input() for i in range(h)]

cnt = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            cnt[i][j] = 0

ans = 0
f = True
while f:
    f = False
    for i in range(h):
        for j in range(w):
            if cnt[i][j] != ans:
                if cnt[i][j]==-1 or cnt[i][j]>ans:
                    f = True
                continue
            for k,l in [[-1,0],[1,0],[0,-1],[0,1]]:
                if 0<=i+k<h and 0<=j+l<w and cnt[i+k][j+l]==-1:
                    cnt[i+k][j+l] = ans+1
    if f:ans += 1
print(ans)



Fixed submission:
h,w = map(int,input().split())
a = [input() for i in range(h)]

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    ans = max(ans,cnt)
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<h and 0<=j+l<w:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = 0
def nibutan(d):
    if len(d)==n:
        global ans
        x = y = 0
        for i in range(n):
            if d[i]==1:
                x += v[i]
                y += c[i]
        ans = max(ans,x-y)
    else:
        nibutan(d+[1])
        nibutan(d+[0])
nibutan([])
print(ans)



Fixed submission:
n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
x = y = 0
for i in range(n):
    if v[i]>c[i]:
        x += v[i]
        y += c[i]
print(x-y)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

from math import gcd
l,r = [0]*(n+1),[0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i],a[i])
    r[n-i-1] = gcd(r[i+1],a[n-i-1])

ans = 1
for i in range(n):
    g = gcd(l[i],r[i+1])
    ans = max(ans,g)
print(ans)

Fixed submission:
import fractions
n = int(input())
a = list(map(int,input().split()))
ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] =  fractions.gcd(l[i],a[i])
for i in range(n-1,0,-1):
    r[i] =  fractions.gcd(r[i+1],a[i])
for i in range(n):
    L = l[i]
    R = r[i+1]
    ans = max(ans,fractions.gcd(L,R))
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
s = input()
a = []
c = 1
for i in range(n-1):
    if s[i]==s[i+1]:
        c+=1
    else:
        a.append(c)
        c = 1
a.append(c)
b = [0]
for i in range(len(a)):
    b.append(b[-1]+a[i])
b.append(b[-1])
l = 2*k+1
st=int(s[0])
ans = 0
for i in range(st,n,2):
    ans = max(ans,b[i]-b[max(0,i-l)])
print(ans)


Fixed submission:
n,k = map(int,input().split())
s = input()
a = []
c = 1
for i in range(n-1):
    if s[i]==s[i+1]:
        c+=1
    else:
        a.append(c)
        c = 1
a.append(c)
b = [0]
for i in range(len(a)):
    b.append(b[-1]+a[i])
b.append(b[-1])
n = len(b)
l = 2*k+1
st=int(s[0])
ans = 0
for i in range(st,n,2):
    ans = max(ans,b[i]-b[max(0,i-l)])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

buf = []
for i in range(x):
    for j in range(y):
        buf.append(a[i]+b[j])

buf = sorted(buf,reverse=True)[:k]
ans = []

for i in buf:
    for j in range(z):
        ans.append(i+c[j])

ans = sorted(ans,reverse=True)
[print(ans[i]) for i in range(k)]


Fixed submission:
x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)

buf = []
for i in range(x):
    for j in range(y):
        buf.append(a[i]+b[j])

buf = sorted(buf,reverse=True)[:k]
ans = []

for i in buf:
    for j in range(z):
        ans.append(i+c[j])

ans = sorted(ans,reverse=True)
[print(ans[i]) for i in range(k)]
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = list(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    a = ''.join(s[l-1:r])
    ans.append(a.count('AC'))
[print(i) for i in ans]

Fixed submission:
n,q = map(int,input().split())
s = input()
dp = [0]*(n+1)
ans = []
for i in range(n):
    dp[i+1] = dp[i]+(1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l,r = map(int,input().split())
    ans.append(dp[r-1]-dp[l-1])
[print(i) for i in ans]
Buggy python submission (verdict: Runtime Error):
from collections import deque
n,k = map(int,input().split())
td = [list(map(int,input().split())) for i in range(n)]
td.sort(key=lambda x:x[1],reverse=True)
a = 0
ans = []
kind = [-1]*n
c = 0
min_p = deque()
for i in range(n):
    eat = False
    if i<k:
        a += td[i][1]
        eat = True
    else:
        if min_p!=[]:
            if kind[td[i][0]-1]<0:
                a -= (min_p[-1]-td[i][1])
                a += (c+1)**2-c**2
                ans.append(a)
                min_p.popleft()
                eat = True
    if eat:
        if kind[td[i][0]-1]<0:
            kind[td[i][0]-1]=1
            c+=1
        else:min_p.append(td[i][1])
    if i==k-1:
        a += c**2
        ans.append(a)
print(max(ans))



Fixed submission:
n,k = map(int,input().split())
td = [list(map(int,input().split())) for i in range(n)]
td.sort(key=lambda x:x[1],reverse=True)
a = 0
ans = []
kind = [-1]*n
c = 0
min_p = []
for i in range(n):
    eat = False
    if i<k:
        a += td[i][1]
        eat = True
    else:
        if min_p:
            if kind[td[i][0]-1]<0:
                a -= (min_p.pop()-td[i][1])
                a += (c+1)**2-c**2
                ans.append(a)
                eat = True
    if eat:
        if kind[td[i][0]-1]<0:
            kind[td[i][0]-1]=1
            c+=1
        else:min_p.append(td[i][1])
    if i==k-1:
        a += c**2
        ans.append(a)
print(max(ans))
Buggy python submission (verdict: Runtime Error):
s = input()
k = 'keyence'
i = 0
inds = []
ans = 'NO'
for a,x in enumerate(s):
    if x==k[i]:
        i+=1
        inds.append(a)
    if i==6:
        c = 0
        for z in range(i-1):
            if inds[z+1]-inds[z]>1:
                c+=1
        if c<=1:ans='YES'
print(ans)

Fixed submission:
s = input()
ans = 'NO'
for i in range(len(s)):
    for j in range(i,len(s)+1):
        if s[:i]+s[j:]=='keyence':
            ans = 'YES'
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
py = []
for i in range(m):
    p,y = map(int,input().split())
    py.append([p,y])
spy = sorted(py,key=lambda x:x[1])

cnt = [0]*n
id = []
for i in spy:
    p,y = i
    cnt[p-1] += 1
    id.append(str(p).zfill(6)+str(cnt[p-1]).zfill(6))

for i in py:
    index = spy.index(i)
    print(id[index])

Fixed submission:
from collections import defaultdict 
n,m = map(int,input().split())
py = []
for i in range(m):
    p,y = map(int,input().split())
    py.append([p,y])
spy = sorted(py,key=lambda x:x[1])

cnt = [0]*n
id =  defaultdict(int)
for i in spy:
    p,y = i
    cnt[p-1] += 1
    id[(p,y)] = str(p).zfill(6)+str(cnt[p-1]).zfill(6)

for i in py:
    p,y = i
    print(id[(p,y)])
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
ans = 1
for i in range(1,m+1):
    if m%i==0:
        x = m//i
        if x>=n:
            ans = i
        else:
            break
print(ans)

Fixed submission:
n,m = map(int,input().split())
ans = 1
for i in range(1,int(m**0.5)+1):
    if m%i==0:
        x = m//i
        if x>=n:
            ans = max(ans,i)
        if i>=n:
            ans = max(ans,x)
        
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    a[i] = a[i]-(i+1)

a.sort()
if i%2==1:
    b = a[i//2]
else:
    b = (a[i//2]+a[i//2+1])//2

ans = 0
for i in range(n):
    ans += abs(a[i]-b)
print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))

for i in range(n):
    a[i] = a[i]-(i+1)

a.sort()
b = (a[n//2]+a[(n-1)//2])//2

ans = 0
for i in range(n):
    ans += abs(a[i]-b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

import math

ans = float('inf')
def calc(x,cnt):
    if x<6:
        global ans
        ans = min(ans,x+cnt)
    else:
        c = 6**int(math.log(x,6))
        if c*6==x:c*=6
        calc(x-c,cnt+1)
        c = 9**int(math.log(x,9))
        if c*9==x:c*=9
        calc(x-c,cnt+1)

calc(n,0)

print(ans)


Fixed submission:
n = int(input())
ans = n
for i in range(n+1):
    c = 0
    t = i
    while t>0:
        c+=t%6
        t //= 6
    t = n-i
    while t>0:
        c+=t%9
        t //= 9
    ans = min(ans,c)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
l = len(s)
sub = [s]
for i in range(0,l):
    for j in range(1,l):
        sub.append(s[i:i+j])
sub = set(sub)
print(sorted(sub)[k-1])

Fixed submission:
s = input()
k = int(input())
l = len(s)
sub = set()
for i in range(l):
    for j in range(1,k+1):
        sub.add(s[i:i+j])
print(sorted(sub)[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
l = len(s)
sub = [s]
for i in range(0,l):
    for j in range(1,l):
        if not s[i:i+j] in sub:
            sub.append(s[i:i+j])
sub.sort()
print(sub[k-1])

Fixed submission:
s = input()
k = int(input())
l = len(s)
sub = set()
for i in range(l):
    for j in range(1,k+1):
        sub.add(s[i:i+j])
print(sorted(sub)[k-1])
Buggy python submission (verdict: Runtime Error):
import re
a,b = map(int,input().split())
s = input()
if s[a]=='-' and re.fullmatch(r'\d+',s[:a]) and re.fullmatch(r'\d+',s[a+1:]):
    print('Yes')
else:
    print('No')
    

Fixed submission:
a,b = map(int,input().split())
s = input()
if s[a]=='-' and s.count('-')==1:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
a = [list(map(int,input().split())) for _ in range(h)]
n = 10
from scipy.sparse.csgraph import floyd_warshall
c = floyd_warshall(c)
ans = 0
for i in a:
    for j in i:
        if j!=-1: ans += c[j][1]
print(int(ans))

Fixed submission:
import itertools
import collections
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
a = [list(map(int,input().split())) for _ in range(h)]
a = list(itertools.chain.from_iterable(a))
b = collections.Counter(a)
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in b:
    if not i in [1,-1]:
        s = 10**9
        bfs([i])
        ans += s*b[i]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
a = [list(map(int,input().split())) for _ in range(h)]
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in range(h):
    for j in range(w):
        if not a[i][j] in [1,-1]:
            s = 10**9
            bfs([a[i][j]])
            ans += s
print(ans)

Fixed submission:
import itertools
import collections
h,w = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(10)]
a = [list(map(int,input().split())) for _ in range(h)]
a = list(itertools.chain.from_iterable(a))
b = collections.Counter(a)
ans = 0

def bfs(x):
    if x[-1]==1:
        global s
        buf = 0
        for i in range(len(x)-1):
            buf += c[x[i]][x[i+1]]
        s = min(s,buf)
    else:
        for i in range(10):
            if not i in x:
                bfs(x+[i])

for i in b:
    if not i in [1,-1]:
        s = 10**9
        bfs([i])
        ans += s*b[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
import bisect
ans = 0
for i in a:
    comb = 1
    index = bisect.bisect_right(b,i)
    for j in b[index:]:
        ans += n-bisect.bisect_right(c,j)
print(ans)

Fixed submission:
n = int(input())
a,b,c = [sorted(list(map(int,input().split())),reverse=True) for i in range(3)]
comp1 = []
i,j = 0,0
cnt = 0
while i<n:
    while j<n and b[j]>a[i]:
        cnt+=1
        j+=1
    comp1.append(cnt)
    i+=1
comp2 = []
i,j = 0,0
cnt = 0
while i<n:
    while j<n and c[j]>b[i]:
        cnt+=1
        j+=1
    comp2.append(cnt)
    i+=1
x = [0]
for i in range(n):
    x.append(x[i]+comp2[i])
ans = 0
for i in comp1:
    ans += x[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
for h in range(1,3500):
    for n in range(1,3500):
        d = N*n+N*h-4*h*n
        if d!=0:
            w = N*h*n/d
            if w.is_integer(): 
                w = int(max(w,-w))
                ans = [h,n,w]
print(ans)

Fixed submission:
import math
N = int(input())
for h in range(1,3501):
    for n in range(1,h):
        d = 4*h*n-N*n-N*h
        if d>0:
            w = N*h*n/d
            if w.is_integer():ans = [h,n,int(w)]
print(ans[0],ans[1],ans[2])
Buggy python submission (verdict: Runtime Error):
n = int(input())
d = [0]*(10**5+1)
for i in range(n):
    a = int(input())
    d[a] += 1
ans = 0
for i in d:
    if i%2==1:
        ans += 1
print(ans)

Fixed submission:
import collections
n = int(input())
a = [int(input()) for _ in range(n)]
c = collections.Counter(a)
ans = 0
for i in c:
    if c[i]%2==1:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
n = int(input())
ans = 1
for i in range(n):
    t = int(input())
    if ans%t!=0:
        ans = ans*t//gcd(ans,t)
print(ans)

Fixed submission:
from fractions import gcd
n = int(input())
ans = 1
for i in range(n):
    t = int(input())
    if ans%t!=0:
        ans = ans*t//gcd(ans,t)
print(ans)
Buggy python submission (verdict: Runtime Error):
k = int(input())

tasu = k // 2
lst = list(range(tasu, tasu+2))
amari = k % 2
for i in range(amari):
    idx = 2 - i
    lst[idx] += 1

print(2)
print(' '.join(map(str, lst)))


Fixed submission:
k = int(input())

n = 50
a = k//n
m = k%n
ans = list(range(a,a+n))
for i in range(m):
    ans[n-i-1] += 1

print(50)
print(*ans)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))
from math import gcd
g = a[0]
for i in a[1:]:
    g = gcd(g,i)
if k<=max(a) and k%g==0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
from fractions import gcd
g = a[0]
for i in a[1:]:
    g = gcd(g,i)
if k<=max(a) and k%g==0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
c = 1
x = a[1]-a[0]
for i in range(1,n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
print(c)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
c = 1
x = 0
for i in range(n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
    elif y!=0:x=y
print(c)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
c = 1
x = a[1]-a[0]
for i in range(1,n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i!=n-2:x = a[i+2]-a[i+1]
        c+=1
print(c)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
c = 1
x = 0
for i in range(n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
    elif y!=0:x=y
print(c)
Buggy python submission (verdict: Runtime Error):
x = int(input())
ans = 10**9
def bfs(i,a):
    if a == x:
        global ans
        ans = min(ans,i-1)
    elif i<=x:
        bfs(i+1,a+i)
        bfs(i+1,a)
        bfs(i+1,a-i)
bfs(0,0)
print(ans)

Fixed submission:
x = int(input())
ans = i = 0
while i<x:
    i += ans
    ans += 1
print(ans-1)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
p = [input()[0] for i in range(n)]
from collections import Counter
c = Counter(p)
v = list(c.values())
ans = 0
while len(v)>=k:
    c = 0
    while c<k and len(v)!=0:
        if v[c]==0:
            v.pop(c)
        else:
            v[c] -= 1
            c+=1
    if c==k:ans += 1
print(ans)

Fixed submission:
n,k = map(int,input().split())
p = [input()[0] for i in range(n)]
from collections import Counter
c = Counter(p)
v = sorted(list(c.values()),reverse=True)
ans = 0
while len(v)>=k:
    for i in range(k):
        v[i] -= 1
        if v[i]<0:
            print(ans)
            exit()
    ans += 1
    v = sorted(v,reverse=True)
print(ans)

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
p = [input()[0] for i in range(n)]
from collections import Counter
c = Counter(p)
v = list(c.values())
ans = 0
while len(v)>=k:
    c = 0
    while c<3 and len(v)!=0:
        if v[c]==0:
            v.pop(c)
        else:
            v[c] -= 1
            c+=1
    if c==3:ans += 1
print(ans)


Fixed submission:
n,k = map(int,input().split())
p = [input()[0] for i in range(n)]
from collections import Counter
c = Counter(p)
v = sorted(list(c.values()),reverse=True)
ans = 0
while len(v)>=k:
    for i in range(k):
        v[i] -= 1
        if v[i]<0:
            print(ans)
            exit()
    ans += 1
    v = sorted(v,reverse=True)
print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input())
k = int(input())
n = len(s)
for i in range(n):
    d = ord('z')-ord(s[i])+1
    if d<=k:
        s[i] = 'a'
        k -= d

s[-1] = chr(ord(s[-1])+k)

print(''.join(s))

Fixed submission:
s = list(input())
k = int(input())
n = len(s)
for i in range(n-1):
    d = (ord('z')-ord(s[i])+1)%26
    if d<=k:
        s[i] = 'a'
        k -= d

x = ord(s[-1])+k%26
if x>ord('z'):x-=26
s[-1] = chr(x)


print(''.join(s))
Buggy python submission (verdict: Runtime Error):
n = int(input())
ans = 0
for i in range(1, n + 1):
    ans += ((n // i) * (2 * i + (n // i)  - 1) * i)) // 2
print(ans)

Fixed submission:
def calc(n, a, d):
    return (n * (2 * a + (n - 1) * d)) // 2


n = int(input())
ans = 0
for i in range(1, n + 1):
    n_ = (n // i)
    d, a = i, i
    sm = calc(n_, a, d)
    ans += sm
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != n - 1 and A[i + 1] == a:
        continue
    do_count = True
    for j in range(i):
        b = A[j]
        if a % b == 0:
            do_count = False
            break
    if do_count:
        ans += 1
print(ans)


Fixed submission:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
lim = A[-1]
se = [True for i in range(lim + 1)]
ans = 0
for i, a in enumerate(A):
    if se[a]:
        if not((i != n - 1 and A[i + 1] == a) or (i != 0 and A[i - 1] == a)):
            ans += 1
        tmp = a
        while not tmp > lim:
            se[tmp] = False
            tmp += a
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if j - i == A[i] + A[j]:
            ans += 1
print(ans)


Fixed submission:
n = int(input())
A = [int(x) for x in input().split()]
backward = [0] * n
forward = [0] * n
for i, a in enumerate(A):
    if i + a < n:
        forward[i + a] += 1
    if i - a >= 0:
        backward[i - a] += 1
ans = 0
for x, y in zip(forward, backward):
    ans += x * y
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()

# keyは(色、jの位置)のタプル
dp = {}

ans = 0

for i in range(n - 2):
    c_i = S[i]
    for j in range(i + 1, n - 1):
        if S[j] == c_i:
            continue
        c_j = S[j]
        d_ij = j - i
        if (c_i, c_j, j) in dp:
            ans += dp[(c_i, c_j, j)]
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    ans -= 1
        else:
            tmp = 0
            for k in range(j + 1, n):
                c_k = S[k]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp += 1
            dp[(c_i, c_j, j)] = tmp
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp -= 1
            ans += tmp
print(ans)


Fixed submission:
n = int(input())
S = input()

# keyは(色、jの位置)のタプル
dp = {}

ans = 0

for i in range(n - 2):
    c_i = S[i]
    for j in range(i + 1, n - 1):
        if S[j] == c_i:
            continue
        c_j = S[j]
        d_ij = j - i
        if (c_i, j) in dp:
            ans += dp[(c_i, j)]
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    ans -= 1
        else:
            tmp = 0
            for k in range(j + 1, n):
                c_k = S[k]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp += 1
            dp[(c_i, j)] = tmp
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp -= 1
            ans += tmp
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = [(1 + int(x)) / 2 for x in input().split()]
ans = 0
for i in range(n - k + 1):
    ans = max(ans, sum(p[i: i + k]))
print(ans)


Fixed submission:
n, k = map(int, input().split())
p = [(1 + int(x)) / 2 for x in input().split()]
a_idx, l, r = 0, 0, 0
for i in range(1, n - k + 1):
    l += p[i - 1]
    r += p[i + k - 1]
    if r > l:
        a_idx, l, r = i, 0, 0
print(sum(p[a_idx:a_idx + k]))