Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= T
            sum_a -= A
            if sum_t < t or sum_a < a:
                sum_t += T
                sum_a += A
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)


Fixed submission:
import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print(t + a)

Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
L = []
for _ in range(N):
    t, a = map(int, input().split())
    L.append([t, a])

t = 0
a = 0
for i in range(N):
    if i == 0:
        t += L[i][0]
        a += L[i][1]
        continue
    if (L[i][0] >= t and L[i][1] >= a):
        t = L[i][0]
        a = L[i][1]
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (L[i][0], L[i][1]) != (tg, ag):
        sum_t, sum_a = L[i][0] * max_ta, L[i][1] * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= L[i][0]
            sum_a -= L[i][1]
            if sum_t < t or sum_a < a:
                sum_t += L[i][0]
                sum_a += L[i][1]
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)


Fixed submission:
import math
N = int(input())

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print(t + a)
Buggy python submission (verdict: Runtime Error):
N, A = map(int, input().split())
X = [0] + list(map(int, input().split()))

max_X = max(X)
dp = [[[0 for k in range((N + 1) * max_X)]
       for j in range(N + 1)] for i in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 1

for j in range(1, N + 1):
    for k in range(1, j + 1):
        for s in range((N + 1) * max_X):
            if s < X[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= X[j]:
                dp[j][k][s] = dp[j - 1][k - 1][s - X[j]] + dp[j - 1][k][s]
ans = 0
for k in range(1, N + 1):
    ans += dp[N][k][k * A]
print(ans)


Fixed submission:
N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

Buggy python submission (verdict: Runtime Error):
N, A = map(int, input().split())
X = [0] + list(map(int, input().split()))

dp = [[[0 for k in range((N + 1) * max(X))]
       for j in range(N + 1)] for i in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 1

for j in range(1, N + 1):
    for k in range(1, j + 1):
        for s in range((N + 1) * max(X)):
            if s < X[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif s >= X[j]:
                dp[j][k][s] = dp[j - 1][k - 1][s - X[j]] + dp[j - 1][k][s]
ans = 0
for k in range(1, N + 1):
    ans += dp[N][k][k * A]
print(ans)

Fixed submission:
N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, A = map(int, input().split())
X = list(map(int, input().split()))

count = 0
for i in range(2 ** N):
    check = []
    for j in range(N):
        if ((i >> j) & 1):
            check.append(X[j])
    # print(check)
    if len(check) > 0 and (sum(check) / len(check)) == A:
        count += 1

print(count)


Fixed submission:
N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())


if (n%2 == 1):
    print((n-1)*3)
elif (n==2):
    print(3)
else:
    k=n/2
    if (x<k):
        if((n/2)%2==0):
            l = []
            for i in range(1,k-2):
                l.append(((n-1)*3)-3*(x-1))
            last = l[0]
            l.append(last)
            print(l[x-1])
        else:
            if (x%2==0):
                print((n-2)*3)
            else:
                print((n-1)*3)
    elif(x==k):
        print(int(k*3))
    else:
        p = n-x
        if (p<k):
            if((n/2)%2==0):
                l = []
                for i in range(1,k-2):
                    l.append(((n-1)*3)-3*(p-1))
                last = l[0]
                l.append(last)
                print(l[p-1])
            else:
                if (p%2==0):
                    print((n-2)*3)
                else:
                    print((n-1)*3)


Fixed submission:
n, x = map(int, input().split())
a, b = max(n-x,x),min(n-x,x)
res = a+b
while b!=0:
    q = a//b
    r = a%b
    res += (b*2)*q
    if (r==0):
        res -= b
    a, b = b, r

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = 0

for i in range(len(A)-1):
  for j in range(i+1,len(A)):
    ans = (ans + A[i]*A[j])%1000000007

print(ans)

Fixed submission:
N = int(input())
a = list(map(int,input().split()))
#a = [100]*N
A = dict(zip(list(range(len(a))),a))
ans = 0
suma = 0
suma = sum(a)

for i in range(len(a)-1):
  suma -= A[i]
  ans = (ans + A[i]*suma)%1000000007
  
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
arr = map(int, input().split())
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)

Fixed submission:
n = int(input())
arr = list(map(int, input().split()))
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)
Buggy python submission (verdict: Runtime Error):
def isEven(num):
  if num%2 == 0:
  	return True
  return False

def isOdd(num):
  if num%2 == 1:
    return True
  return False

if __name__ == "__main__":
  x,k,d = map(int, input().split())
  div = x//d
  cmp = x
  defo = x
  if isOdd(k):
    if x > d:
      if k%div != 0:
        div = min(div,k%div)
      for i in [d,-d]:
        cmp = min(cmp,abs(defo+div*i))
      print(cmp)
    else:
      for i in [d,-d]:
        cmp = min(cmp,abs(defo+i))
      print(cmp)
  if isEven(k):
    div = x//(2*d)
    if x > d:
      div = min(div,k)
      for j in range(1,div)
        for i in [d,-d]:
          cmp = min(cmp,abs(defo+(2*j)*i))
      print(cmp)
    else:
      print(cmp)

Fixed submission:
x,k,d = map(int,input().split())
x = abs(x)
div = min(x//d,k)
cnt = 0
k-=div
x -= div*d
if k%2 == 0:
  print(x)
else:
  print(abs(x-d))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import math

a = int(input())
cnt = 0
ans = []
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans.append(x*x+y*y+z*z+x*y+y*z+z*x)

for i in range(1,a+1):
    print(ans.count(i))

Fixed submission:
import itertools
import math

a = int(input())
cnt = 0
ans = [0]*100000
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans[x*x+y*y+z*z+x*y+y*z+z*x]+=1

for i in range(1,a+1):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import math
a = int(input())

def calc(x,y,z,n):
  if(n==x*x+y*y+z*z+x*y+y*z+z*x):
    return True

for i in range(1,a+1):
  l = list(range(1,int(math.sqrt(a))))
  cnt = 0;
  for x,y,z in itertools.product(l, repeat=3):
    if(calc(x,y,z,i)):
      cnt+=1;
  print(cnt)

Fixed submission:
import itertools
import math

a = int(input())
cnt = 0
ans = [0]*100000
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans[x*x+y*y+z*z+x*y+y*z+z*x]+=1

for i in range(1,a+1):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input().split())
c = []
for _ in range(a):
	c.append(int(input()))
sort(c)
print(sum(c[0:b]))

Fixed submission:
a,b = map(int,input().split())
c = list(map(int,input().split()))
c.sort()
print(sum(c[0:b]))
Buggy python submission (verdict: Runtime Error):
arr = map(int, input().split())
for i in range(len(arr)):
  if (arr[i] == 0):
    print(i+1)

Fixed submission:
arr = list(map(int, input().split()))
for i in range(len(arr)):
  if (arr[i] == 0):
    print(i+1)
Buggy python submission (verdict: Runtime Error):
def main()
	n = int(input())
  	arr = list(map(input().split()))
    if 0 in arr:
        print(0)
        return
    prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            print(-1)
            return
    print(prod)

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    arr = list(map(int, input().split()))
    if 0 in arr:
        print(0)
        return
    prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            print(-1)
            return
    print(prod)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main()
	n = input()
  	arr = list(map(input().split()))
    if 0 in arr:
        print(0)
        return
  	prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            print(-1)
            return
    print(prod)

if __name__ = "__main__":
	main()

Fixed submission:
def main():
    n = int(input())
    arr = list(map(int, input().split()))
    if 0 in arr:
        print(0)
        return
    prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            print(-1)
            return
    print(prod)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main()
	n = input()
  	arr = list(map(input().split()))
    if 0 in arr:
        return print(0)
  	prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            return print(-1)
    print(prod)

if __name__ = "__main__":
	main()

Fixed submission:
def main():
    n = int(input())
    arr = list(map(int, input().split()))
    if 0 in arr:
        print(0)
        return
    prod = 1
    for x in arr:
        prod *= x
        if prod > int(1e18):
            print(-1)
            return
    print(prod)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
k = int(input())
a = str(input())

if len(a) <= k:
	print(a)
else
	print(a[:k] + "...")

Fixed submission:
k = int(input())
a = str(input())
 
if len(a) <= k:
	print(a)
else:
	print(a[:k] + "...")
Buggy python submission (verdict: Runtime Error):
def main(x):
  for i in range(100):
    for j in range(100):
      if(i**5-j**5 == x):
        print(str(i)+" "+str(j))
        return

if __name__ = '__main__':
  main(input())

Fixed submission:
def main(x):
  for i in range(-120,120):
    for j in range(-120,120):
      if(i**5-j**5 == int(x)):
        print(str(i)+" "+str(j))
        return
 
if __name__ == '__main__':
  main(input())

Buggy python submission (verdict: Runtime Error):
x = input()
for i in range(100):
  for j in range(100):
    if(i**5-j**5 == x):
      print(str(i)+" "+str(j))
      return

Fixed submission:
def main(x):
  for i in range(-120,120):
    for j in range(-120,120):
      if(i**5-j**5 == int(x)):
        print(str(i)+" "+str(j))
        return
 
if __name__ == '__main__':
  main(input())

Buggy python submission (verdict: Runtime Error):
x = input()
for i in range(100):
  for j in range(100):
	if(i**5-j**5 == x):
      print(str(i)+" "+str(j))

Fixed submission:
def main(x):
  for i in range(-120,120):
    for j in range(-120,120):
      if(i**5-j**5 == int(x)):
        print(str(i)+" "+str(j))
        return
 
if __name__ == '__main__':
  main(input())
Buggy python submission (verdict: Runtime Error):
s = input()
if(s[2]!=s[3] || s[4]!=s[5]):
  print("No")
  exit()
else:
  print("Yes")

Fixed submission:
s = input()
if(s[2]!=s[3] or s[4]!=s[5]):
  print("No")
  exit()
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
string = input()
mid = len(s)//2

gnirts = reversed(string)
print(gnirts)
if(string != gnirts or string[:mid-1] != gnirts[mid+1:] or string[mid+1:] != gnirts[:mid-1]):
  print("No")
  exit()
print("Yes")

Fixed submission:
string = input()
mid = len(string)//2

gnirts = string[::-1]
if(string != gnirts or string[:mid] != gnirts[mid+1:] or string[mid+1:] != gnirts[:mid]):
  print("No")
  exit()
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
a = int(input())
aa = []
for i in range(a):
    n = input()
    if aa.count(n) == 0:
        aa.append(n)
print(len(aa))

Fixed submission:
a = int(input())
aaa = set([])
for i in range(a):
    n = input()
    aaa.add(n)
print(len(aaa))
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

su = 0
N = int(input())
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            su += gcd(i,j,k)
print(su)

Fixed submission:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

su = 0
N = int(input())
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            su += gcd(i,j,k)
su *= 6
for x in range(1,N+1):
    for y in range(1,N+1):
        if x != y:
            su += 3*(gcd(x,y))
        else:
            su += x
print(su)
Buggy python submission (verdict: Runtime Error):
a,b = list(map(int,input().split()))
A = []
list = [["" for i in range(b)] for j in range(a)]
for i in range(a):
    n = input()
    if n.count(".") == b:
       pass 
    else:
        for j in range(b):
            list[i][j] = n[j]
for i in range(b):
    for j in range(a):
        A.append(list[j][i])
    if len(A) == A.count(".")+A.count(""):
        for k in range(a):
            list[k][i] = ""
    A = []
for i in range(a):
    for j in range(b):
        if list[i][j] != "":
            print(list[i][j],end="")
            AAA = 1
    if AAA == 1:
        print()
    AAA = 0

Fixed submission:
a,b = list(map(int,input().split()))
A = []
AAA = 0
list = [["" for i in range(b)] for j in range(a)]
for i in range(a):
    n = input()
    if n.count(".") == b:
       pass 
    else:
        for j in range(b):
            list[i][j] = n[j]
for i in range(b):
    for j in range(a):
        A.append(list[j][i])
    if len(A) == A.count(".")+A.count(""):
        for k in range(a):
            list[k][i] = ""
    A = []
for i in range(a):
    for j in range(b):
        if list[i][j] != "":
            print(list[i][j],end="")
            AAA = 1
    if AAA == 1:
        print()
    AAA = 0
Buggy python submission (verdict: Runtime Error):
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

input = sys.stdin.readline
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)

print(uf.group_count() - 1)

Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

input = sys.stdin.readline
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

print(uf.group_count() - 1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1, N):
    if dp[i] == 0:
        continue
    for s in S:
        if i + s <= N:
            dp[s+i] += dp[i]
            dp[s+i] %= mod

print(dp[N])

Fixed submission:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        # print("left", left, "right", right)
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod

# print(acc)
print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1, N):
    for s in S:
        if i + s <= N:
            dp[s+i] += dp[i]
            dp[s+i] %= mod

print(dp[N])

Fixed submission:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        # print("left", left, "right", right)
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod

# print(acc)
print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        S.add(i)

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
for i in range(1, N):
    for s in S:
        if i + s <= N:
            dp[s+i] += dp[i]
            dp[s+i] %= mod

print(dp[N])

Fixed submission:
import sys

input = sys.stdin.readline

N, K = map(int, input().split())
S = set()
for _ in range(K):
    l, r = map(int, input().split())
    S.add((l, r))

mod = 998244353
dp = [0 for _ in range(N+1)]
dp[1] = 1
acc = [0 for _ in range(N+1)]
acc[1] = 1
for i in range(1, N+1):
    for (l, r) in S:
        left = max(i - r - 1, 0)
        right = max(i - l, 0)
        # print("left", left, "right", right)
        dp[i] += acc[right] - acc[left]
        dp[i] %= mod
    acc[i] = acc[i-1] + dp[i]
    acc[i] %= mod

# print(acc)
print(dp[N])
Buggy python submission (verdict: Runtime Error):
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()
if K == 0:
    print(A[-1])
else:
    ans = 10**9
    l = 0
    r = 10**9
    while l < r:
        # t以下の長さにするのに必要な切る回数
        t = (l + r) // 2
        # print(t)
        n = K
        for a in A:
            n -= (a - 1) // t
            if n < 0:
                break
        if n >= 0:
            ans = min(ans, t)
        if n >= 0:
            r = t
        else:
            l = t + 1

    print(ans)

Fixed submission:
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()
if K == 0:
    print(A[-1])
else:
    ans = 10**9
    l = 0
    r = 10**9
    while l < r:
        # t以下の長さにするのに必要な切る回数
        t = (l + r) // 2
        if t == 0:
            break
        # print(t)
        n = K
        for a in A:
            n -= (a - 1) // t
            if n < 0:
                break
        if n >= 0:
            ans = min(ans, t)
        if n >= 0:
            r = t
        else:
            l = t + 1

    print(ans)