Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
from math import gcd
n, x, d = map(int, input().split())

if d == 0:
	print(n+1)
	sys.exit()

if d < 0:
	x, d = -x, -d

ans = n
g = gcd(x, d)

for i in range(2, n+1):
	k = max(((i - d//g) * (2*n - 1 - i + d//g)) // 2 - x//g, -1)
	ans += max((i * (2*n-1-i)) // 2 - k, 0)

print(ans)

Fixed submission:
import sys
from fractions import gcd
n, x, d = map(int, input().split())
"""
数列からi個選ぶことを考えると
i*xに加えて足されるdの数はi(i-1)/2 〜 i(2n-1-i)/2 の任意の個数
i > j なるjで代替されるような和はこのうちどのような条件を満たすものか？
g = gcd(x, d). l = lcm(x, d)として
(g*l = x*d)
i*x + k*d が条件を満たすとすると
i*x + k*d = (i - d/g)x + (k + x/g)d が成り立つ
(i - d/g)(2n - 1 - i + d/g)/2 >= (k + x/g) となるような最大のkを求めれば，
k以下はすべてかぶる，k+1以上はすべてかぶらない

x<0 のときは
(i - d//g) * (i - d//g - 1)//2 <= (k + x//g) <= (i - d//g) * (2*n - 1 - i + d//g)//2
(i - d//g) * (i - d//g - 1)//2 - x//g <= k <= (i - d//g) * (2*n - 1 - i + d//g)//2 - x//g
となるようなkにおいてはかぶる
"""
if x == 0 and d == 0:
	print(1)
	sys.exit()
elif d == 0:
	print(n+1)
	sys.exit()

if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d

if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d

#print(x, d)
g = gcd(x, d)

ans = 1
if x >= 0:
	for i in range(1, n+1):
		#print((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g)
		k = max((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (i-1) // 2 - 1)
		#print(k)
		ans += max((i * (2*n-1-i)) // 2 - k, 0)

else:
	for i in range(1, n+1):
		overlap_u = min((i - d//g) * (2*n - 1 - i + d//g) // 2 - x//g, i * (2*n-1-i) // 2)
		overlap_l = max((i - d//g) * (i - d//g - 1) // 2 - x//g, i * (i-1) // 2)
		ans += i * (2*n-1-i) // 2 - i * (i-1) // 2 + 1 - max(overlap_u - overlap_l + 1, 0)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]
n, p = map(int, input().split())
snacks = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
dp = [0 for _ in range(p)]
ans = snacks[0][1]

for i in range(1, n):
	x, y = snacks[i-1]
	z = snacks[i][1]
	for j in range(p-1, 0, -1):
		if j >= x:
			dp[j] = max(dp[j], dp[j-x]+y)
		ans = max(ans, dp[j]+z)

print(ans)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, p = map(int, input().split())
snacks = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
dp = [0 for _ in range(p)]
ans = snacks[0][1]

for i in range(1, n):
	x, y = snacks[i-1]
	z = snacks[i][1]
	for j in range(p-1, 0, -1):
		if j >= x:
			dp[j] = max(dp[j], dp[j-x]+y)
		ans = max(ans, dp[j]+z)

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])
a = [(x[0], i) for i, x in enumerate(c)]
b = [x[1] for x in c]
a.sort()
for i in range(n):
	if a[i][0] > b[i]:
		print("No")
		sys.exit()
cur, cnt = 0, 0
while a[cur][1] != 0:
	cnt += 1
	cur = a[cur][1]
if cnt < n-1:
	print("Yes")
else:
	for i in range(n-1):
		if a[i] <= b[i+1]:
			print("Yes")
			break
	else:
		print("No")

Fixed submission:
import sys
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])
a = [(x[0], i) for i, x in enumerate(c)]
b = [x[1] for x in c]
a.sort()
for i in range(n):
	if a[i][0] > b[i]:
		print("No")
		sys.exit()
cur, cnt = 0, 0
while a[cur][1] != 0:
	cnt += 1
	cur = a[cur][1]
if cnt < n-1:
	print("Yes")
else:
	for i in range(n-1):
		if a[i+1][0] <= b[i]:
			print("Yes")
			break
	else:
		print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
f = sorted(list(map(int, input().split())), reverse=True)

ok, ng = a[-1]*f[0], -1
while ok-ng > 1:
	x = (ok+ng)//2
	tmp = 0
	for i in range(n):
		tmp += max(0, a[i] - x//f[i])
	if tmp > k:
		ng = x
	else:
		ok = x
print(ok)

Fixed submission:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
f = sorted(list(map(int, input().split())), reverse=True)

ok, ng = a[-1]*f[0], -1
while ok-ng > 1:
	x = (ok+ng)//2
	tmp = 0
	for i in range(n):
		tmp += max(0, a[i] - x//f[i])
	if tmp > k:
		ng = x
	else:
		ok = x
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

INF = 10**5
n, m = map(int, input().split())
e = [INF for _ in range(n)]
e[n-1] = 0
adj = [[] for _ in range(n)]
farthest = [0 for _ in range(n)]
for _ in range(m):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)

for x in range(n-2, -1, -1):
	if adj[x] == [n-1]:
		e[x] = 1		
	else:		
		su = 0
		for v in adj[x]:
			su += e[v]
			farthest[x] = max(farthest[x], e[v])
		e[x] = su/len(adj[x]) + 1

ans = e[0]

for i in range(n-1):
	f = e
	if len(adj[i]) == 1:
		f[i] = INF
	else:
		f[i] = ((e[i] - 1) * len(adj[i]) - farthest[i]) / (len(adj[i]) - 1) + 1

	for x in range(i-1, -1, -1):
		if adj[x] == [n-1]:
			f[x] = 1		
		else:		
			su = 0
			for v in adj[x]:
				if f[v] == INF:
					f[x] = INF
					break
				su += f[v]
			else:
				f[x] = su/len(adj[x]) + 1
	ans = min(ans, f[0])

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

INF = 10**5
n, m = map(int, input().split())
e = [INF for _ in range(n)]
e[n-1] = 0
adj = [[] for _ in range(n)]
farthest = [0 for _ in range(n)]
for _ in range(m):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)

for x in range(n-2, -1, -1):
	if adj[x] == [n-1]:
		e[x] = 1		
	else:		
		su = 0
		for v in adj[x]:
			su += e[v]
			farthest[x] = max(farthest[x], e[v])
		e[x] = su/len(adj[x]) + 1

ans = e[0]

for i in range(n-1):
	f = e
	if len(adj[i]) == 1:
		f[i] = INF
	else:
		f[i] = ((e[i] - 1) * len(adj[i]) - farthest[i]) / (len(adj[i]) - 1) + 1

	for x in range(i-1, -1, -1):
		if adj[x] == [n-1]:
			f[x] = 1		
		else:		
			su = 0
			for v in adj[x]:
				if f[v] == INF:
					f[x] = INF
					break
				su += f[v]
			else:
				f[x] = su/len(adj[x]) + 1
	ans = min(ans, f[0])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

#print(*dist, sep="\n")
diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

#print(*dist, sep="\n")
diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ans = 0
#even = []
for i in range(60):
	cnt = 0
	for x in a:
		if (x>>i) & 1:
			cnt += 1
	if cnt%2 == 1:
		ans += (1<<i)
		for j in range(n):
			if (a[j]>>i) & 1:
				a[j] -= (1<<i)
#print(ans, even)

yet = 0
for r in range(59, -1, -1):
	stood = False
	for c in range(yet, n):
		if (a[c]>>r) & 1:
			if not stood:
				stood = True
				a[yet], a[c] = a[c], a[yet]
				yet += 1
	if stood:
		for c in range(n):
			if c == yet-1 or (a[c]>>r) & 1 == 0:
				continue
			#print(c)
			a[c] ^= a[yet-1]

tmp = 0
res = 0
for c in range(n):
	tmp ^= a[c]
	res = max(res, tmp) 

print(ans + (res<<1))

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

ans = 0
#even = []
for i in range(60):
	cnt = 0
	for x in a:
		if (x>>i) & 1:
			cnt += 1
	if cnt%2 == 1:
		ans += (1<<i)
		for j in range(n):
			if (a[j]>>i) & 1:
				a[j] -= (1<<i)
#print(ans, even)

yet = 0
for r in range(59, -1, -1):
	stood = False
	for c in range(yet, n):
		if (a[c]>>r) & 1:
			if not stood:
				stood = True
				a[yet], a[c] = a[c], a[yet]
				yet += 1
	if stood:
		for c in range(n):
			if c == yet-1 or (a[c]>>r) & 1 == 0:
				continue
			#print(c)
			a[c] ^= a[yet-1]

tmp = 0
res = 0
for c in range(n):
	tmp ^= a[c]
	res = max(res, tmp) 

print(ans + (res<<1))
Buggy python submission (verdict: Runtime Error):
import sys
n = int(input())
s = input()
if s[0] == "W":
  print(0)
  sys.exit()
MOD = 10**9+7
ans = 1
cnt = 1
for i in range(2*n):
  if s[i+1] != s[i]:
    cnt += 1
  else:
    ans *= cnt
    ans %= MOD
    cnt -= 1
if cnt != 0:
  print(0)
else:
  print(ans)

Fixed submission:
import sys
n = int(input())
s = input()
if s[0] == "W":
  print(0)
  sys.exit()
MOD = 10**9+7
ans = 1
cnt = 1
right = 1
for i in range(2*n-1):
  if s[i+1] == s[i]:
    right ^= 1
  if right:
    cnt += 1
  else:
    ans *= cnt
    ans %= MOD
    cnt -= 1
if cnt != 0:
  print(0)
else:
  for i in range(1, n+1):
    ans *= i
    ans %= MOD
  print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = ineput()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
pre = ["", ["", ""]]
for i in range(3*n):
  if t != 0 and s[i] not in pre[1]:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      pre[1] = ["", ""]
  elif s[i] == pre[0] or o == 0:
    o += 1
    ans *= z
    ans %= mod
    z -= 1
    pre[0] = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    pre[1] = [pre[0], s[i]]
    if o == 0:
      pre[0] = ""

print(ans)


Fixed submission:
n = int(input())
s = input()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
pre = ["", ["", ""]]
for i in range(3*n):
  if t != 0 and s[i] not in pre[1]:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      pre[1] = ["", ""]
  elif s[i] == pre[0] or o == 0:
    o += 1
    ans *= z
    ans %= mod
    z -= 1
    pre[0] = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    pre[1] = [pre[0], s[i]]
    if o == 0:
      pre[0] = ""

print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
O, T = "", ""
for i in range(3*n):
  if T != "" and s[i] != O and s[i] != T:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      T = ""
  elif s[i] == O or O == "":
    o += 1
    ans *= zg
    ans %= mod
    z -= 1
    O = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    T = s[i]
    if o == 0:
      O = ""

print(ans)


Fixed submission:
n = int(input())
s = input()
mod = 998244353
ans = 1
z, o, t = n, 0, 0
pre = ["", ["", ""]]
for i in range(3*n):
  if t != 0 and s[i] not in pre[1]:
    ans *= t
    ans %= mod
    t -= 1
    if t == 0:
      pre[1] = ["", ""]
  elif s[i] == pre[0] or o == 0:
    o += 1
    ans *= z
    ans %= mod
    z -= 1
    pre[0] = s[i]
  else:
    t += 1
    ans *= o
    ans %= mod
    o -= 1
    pre[1] = [pre[0], s[i]]
    if o == 0:
      pre[0] = ""

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	plus, minus = [], []
	for x in a:
		if x%d == 0:
			continue
		plus.append(d-(x%d))
		minus.append(x%d)
	if min(sum(plus)-max(plus), sum(minus)-max(minus)) <= k:
		print(d)
		break

Fixed submission:
from math import sqrt
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
div = []
for i in range(1, int(sqrt(s)+1)):
	if s%i == 0:
		if i*i != s:
			div.append(s//i)
		div.append(i)
div.sort(reverse=True)
#print(div)

for d in div:
	b = [x%d for x in a if x%d != 0]
	if not b:
		print(d)
		break
	b.sort(key=lambda x: x%d)
	y, z = 0, d*len(b)-sum(b)
	res = 10**30
	for x in b:
		y += x
		z -= d-x
		res = min(res, max(y, z))
	if res <= k:
		print(d)
		break
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])

Fixed submission:
MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
s = input()[::-1]
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j + (10**i)*int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j + (10**i)*k) % 13] += dp[j]
				dpp[(j + (10**i)*k) % 13]  %= MOD
	dp = dpp
print(dp[5])

Fixed submission:
MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
s = input()[::-1]
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j + (10**i)*int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j + (10**i)*k) % 13] += dp[j]
	dp = [dppp%MOD for dppp in dpp]
print(dp[5])

Fixed submission:
MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = len(set(a))
if l > 3:
	print("No")
elif l == 1:
	if a[0] == 0:
		print("Yes")
	else:
		print("No")
elif n%3 != 0:
	print("No")
elif l == 2:
	if 0 not in set(a):
		print("No")
	elif a.count(0) == n//3:
		print("Yes")
	else:
		print("No")
else:
	for x in list(set(a)):
		if a.count(x) != n//3:
			print("No")
			break
	elif list(set(a))[0] ^ list(set(a))[1] == list(set(a))[2]:
		print("Yes")
	else:
		print("No")

Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = len(set(a))
if l > 3:
	print("No")
elif l == 1:
	if a[0] == 0:
		print("Yes")
	else:
		print("No")
elif n%3 != 0:
	print("No")
elif l == 2:
	if 0 not in set(a):
		print("No")
	elif a.count(0) == n//3:
		print("Yes")
	else:
		print("No")
else:
	for x in list(set(a)):
		if a.count(x) != n//3:
			print("No")
			break
	else:
		if list(set(a))[0] ^ list(set(a))[1] == list(set(a))[2]:
			print("Yes")
		else:
			print("No")
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt
n, k = map(int, input().split())
MOD = 10**9 + 7
max1 = int(sqrt(n))
dp1 = [[0 for _ in range(max1+1)] for _ in range(k)]
for j in range(1, max1+1):
	dp1[0][j] = 1
max2 = int(n/(max1+1))
dp2 = [[0 for _ in range(max2+1)] for _ in range(k)]
for j in range(1, max2+1):
	dp2[0][j] = int(n/j) - int(n/(j+1))

for i in range(k-1):
	csum1 = (sum(dp1[i])+sum(dp2[i])) % MOD
	dp1[i+1][1] = csum1
	for j in range(2, max1+1):
		dp1[i+1][j] = (dp1[i+1][j-1] - dp2[i][j-1]) % MOD
	csum2 = sum(dp1[i][:max2+1]) % MOD
	dp2[i+1][max2] = (csum2*dp2[0][max2]) % MOD
	for j in range(max2-1, 0, -1):
		csum2 -= dp1[i][j+1]
		csum2 %= MOD
		dp2[i+1][j] = (csum2*dp2[0][j]) % MOD

print((sum(dp1[k-1])+sum(dp2[k-1]))%MOD)

Fixed submission:
from math import sqrt
n, k = map(int, input().split())
MOD = 10**9 + 7
max1 = int(sqrt(n))
dp1 = [[0 for _ in range(max1+1)] for _ in range(k)]
for j in range(1, max1+1):
	dp1[0][j] = 1
max2 = int(n/(max1+1))
dp2 = [[0 for _ in range(max2+1)] for _ in range(k)]
for j in range(1, max2+1):
	dp2[0][j] = int(n/j) - int(n/(j+1))

for i in range(k-1):
	csum1 = (sum(dp1[i])+sum(dp2[i])) % MOD
	dp1[i+1][1] = csum1
	for j in range(2, max1+1):
		dp1[i+1][j] = (dp1[i+1][j-1] - dp2[i][j-1]) % MOD
	csum2 = sum(dp1[i][:max2+1]) % MOD
	dp2[i+1][max2] = (csum2*dp2[0][max2]) % MOD
	for j in range(max2-1, 0, -1):
		csum2 -= dp1[i][j+1]
		csum2 %= MOD
		dp2[i+1][j] = (csum2*dp2[0][j]) % MOD

print((sum(dp1[k-1])+sum(dp2[k-1]))%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
s = [input() for _ in range(H)]
tate = [[0 for _ in range(W)] for _ in range(H)]
yoko = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
	ba, fr = 0, 0
	while ba < W:
		if s[h][ba] == "#":
			ba += 1
			fr += 1
		while fr < W and s[h][fr] == ".":
			fr += 1
		for w in range(ba, fr):
			yoko[h][w] = fr-ba
		ba = fr
#print(yoko, sep="\n")
for w in range(W):
	ba, fr = 0, 0
	while ba < H:
		if s[ba][w] == "#":
			ba += 1
			fr += 1
		while fr < H and s[fr][w] == ".":
			fr += 1
		for h in range(ba, fr):
			tate[h][w] = fr-ba
		ba = fr
#print(tate, sep="\n")
ans = 1
for h in range(H):
	for w in range(W):
		ans = max(ans, yoko[h][w]+tate[h][w]-1)
print(ans)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
tate = [[0 for _ in range(W)] for _ in range(H)]
yoko = [[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
	ba, fr = 0, 0
	while ba < W:
		if s[h][ba] == "#":
			ba += 1
			fr += 1
		while fr < W and s[h][fr] == ".":
			fr += 1
		for w in range(ba, fr):
			yoko[h][w] = fr-ba
		ba = fr
#print(yoko, sep="\n")
for w in range(W):
	ba, fr = 0, 0
	while ba < H:
		if s[ba][w] == "#":
			ba += 1
			fr += 1
		while fr < H and s[fr][w] == ".":
			fr += 1
		for h in range(ba, fr):
			tate[h][w] = fr-ba
		ba = fr
#print(tate, sep="\n")
ans = 1
for h in range(H):
	for w in range(W):
		ans = max(ans, yoko[h][w]+tate[h][w]-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Fixed submission:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)