Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 30 22:26:37 2019

@author: Owner
"""

MOD = 1000000007

def inv(x):
    return pow(x, MOD - 2, MOD)

B, W = map(int, input().split())
fct = [1] * (B + W + 1)
for i in range(B + W):
    fct[i + 1] = (fct[i] * (i + 1)) % MOD

def c(n, k):
    return (fct[n] * inv(fct[k]) * inv(fct[n - k])) % MOD

#p[i]: 黒B回白i回の確率
#q[i]: 黒i回白W回の確率
p = [0] * W
p[0] = inv(pow(2, B, MOD))
for i in range(W - 1):
    p[i + 1] = (p[i] + c(B + i, i + 1) * inv(pow(2, B + i, MOD)) * inv(2)) % MOD
q = [0] * B
q[0] = inv(pow(2, W, MOD))
for i in range(B - 1):
    q[i + 1] = (q[i] + c(W + i, i + 1) * inv(pow(2, W + i, MOD)) * inv(2)) % MOD
for i in range(B + W):
    if i < min(B, W):
        print(inv(2))
        continue
    if i >= max(B, W):
        print((q[i - W] + (1 - p[i - B] - q[i - W] + MOD) * inv(2)) % MOD)
        continue
    if B < W:
        print(((1 - p[i - B] + MOD) * inv(2)) % MOD)
    else:
        print((q[i - W] + (1 - q[i - W] + MOD) * inv(2)) % MOD)

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 30 22:26:37 2019

@author: Owner
"""

MOD = 1000000007

def inv(x):
    return pow(x, MOD - 2, MOD)

B, W = map(int, input().split())
fct = [1] * (B + W + 1)
for i in range(B + W):
    fct[i + 1] = (fct[i] * (i + 1)) % MOD

def c(n, k):
    return (fct[n] * inv(fct[k]) * inv(fct[n - k])) % MOD

#p[i]: 黒B回白i回の確率
#q[i]: 黒i回白W回の確率
p = [0] * W
p[0] = inv(pow(2, B, MOD))
for i in range(W - 1):
    p[i + 1] = (p[i] + c(B + i, i + 1) * inv(pow(2, B + i, MOD)) * inv(2)) % MOD
q = [0] * B
q[0] = inv(pow(2, W, MOD))
for i in range(B - 1):
    q[i + 1] = (q[i] + c(W + i, i + 1) * inv(pow(2, W + i, MOD)) * inv(2)) % MOD
for i in range(B + W):
    if i < min(B, W):
        print(inv(2))
        continue
    if i >= max(B, W):
        print((q[i - W] + (1 - p[i - B] - q[i - W] + MOD) * inv(2)) % MOD)
        continue
    if B < W:
        print(((1 - p[i - B] + MOD) * inv(2)) % MOD)
    else:
        print((q[i - W] + (1 - q[i - W] + MOD) * inv(2)) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    dp = {}
    for i in range(W + 1):
        dp[0, i] = 0
    for i in range(N):
        for j in range(W + 1):
            if j < w[i]:
                dp[i + 1, j] = dp[i, j]
            else:
                dp[i + 1, j] = max(dp[i, j], dp[i, j - w[i]] +v[i])
    return dp[N, W]

N, W = map(int, input().split())
w = {}
v = {}
for i in range(N):
    w[i], v[i] = map(int, input().split())
print(solve())

Fixed submission:
N, W = map(int, input().split())
dp = [0] * (W + 1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W - w, -1, -1):
        dp[j + w] = max(dp[j + w], dp[j] + v)
print(dp[W])
Buggy python submission (verdict: Runtime Error):
import math
N, P = map(int, input().split())
if N == 1:
	print(P)
elif N > math.log2(P):
	print(1)
else:
	ans = 1
	x = int(P ** (1.0 / (N * 1.0)))
	for i in range(2, x + 1):
		if P % (i ** N) == 0:
			ans = i
	print(ans)

Fixed submission:
import math	
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		if N * math.log(i) > math.log(P):
			break
		if P % (i ** N) == 0:
			ans = i
	print(ans)

Buggy python submission (verdict: Runtime Error):
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		g = i ** N
		if g > P:
			break
		if P % g == 0:
			ans = i
	print(ans)


Fixed submission:
import math	
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		if N * math.log(i) > math.log(P):
			break
		if P % (i ** N) == 0:
			ans = i
	print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		g = i ** N
		if g > P:
			break
		if P % g == 0:
			ans = i
	print(ans)

Fixed submission:
import math	
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		if N * math.log(i) > math.log(P):
			break
		if P % (i ** N) == 0:
			ans = i
	print(ans)
Buggy python submission (verdict: Runtime Error):
def ans(n, x):
	if x < 1:
		return 0
	if x < 2 ** (n + 1) - 1:
		return ans(n - 1, x - 1)
	if x == 2 ** (n + 1) - 1:
		return 2 ** n
	return 2 ** n + ans(n - 1, x - 2 ** (n + 1) + 1)
N, X = map(int, input().split())
print(ans(N, X))

Fixed submission:
def ans(n, x):
	if n < 0:
		return 0
	if x < 1:
		return 0
	if x < 2 ** (n + 1) - 1:
		return ans(n - 1, x - 1)
	if x == 2 ** (n + 1) - 1:
		return 2 ** n
	return 2 ** n + ans(n - 1, x - 2 ** (n + 1) + 1)
N, X = map(int, input().split())
print(ans(N, X))

Buggy python submission (verdict: Runtime Error):
def ans(n, x):
	if x == 0:
		return 0
	if x < 2 ** (n + 1) - 1:
		return ans(n - 1, x - 1)
	if x == 2 ** (n + 1) - 1:
		return 2 ** n
	return 2 ** n + ans(n - 1, x - 2 ** (n + 1) + 1)
N, X = map(int, input().split())
print(ans(N, X))

Fixed submission:
def ans(n, x):
	if n < 0:
		return 0
	if x < 1:
		return 0
	if x < 2 ** (n + 1) - 1:
		return ans(n - 1, x - 1)
	if x == 2 ** (n + 1) - 1:
		return 2 ** n
	return 2 ** n + ans(n - 1, x - 2 ** (n + 1) + 1)
N, X = map(int, input().split())
print(ans(N, X))
Buggy python submission (verdict: Runtime Error):
S = input()
ans = 999
for i in range(S - 2):
  ans = min(ans, abs(753 - int(S[i:i + 3])))
print(ans)

Fixed submission:
S = input()
ans = 999
for i in range(len(S) - 2):
  ans = min(ans, abs(753 - int(S[i:i + 3])))
print(ans)
Buggy python submission (verdict: Runtime Error):
3
1 2 3

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
s = sum(a)
ans = -1
diff = 100000
for i in range(N):
	d = abs(s - a[i] * N)
	if d < diff:
		ans = i
		diff = d
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(N):
	s = 0
	for j in range(i, N):
		s = s + a[j]
		b.append(s)
max_b = len(bin(max(b))) - 2
#print(b, max_b)
ans = 0
for i in range(max_b):
	p = 0
	c = 2 ** (max_b - 1 - i)
	#print("i=",i, "c=",c)
	for j in b:
		if (ans + c) & j == ans + c:
			#print("j=",j)
			p = p + 1
	if p >= K:
		ans = ans + 2 ** (max_b - 1 - i)
		#print("ans=",ans)
print(ans)

Fixed submission:
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(N):
	s = 0
	for j in range(i, N):
		s = s + a[j]
		b.append(s)
max_b = len(bin(max(b))) - 2
#print(b, max_b)
ans = 0
for i in range(max_b):
	p = 0
	c = 2 ** (max_b - 1 - i)
	#print("i=",i, "c=",c)
	for j in b:
		if (ans + c) & j == ans + c:
			#print("j=",j)
			p = p + 1
	if p >= K:
		ans = ans + 2 ** (max_b - 1 - i)
		#print("ans=",ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
def congruence(x, y): #=(a, b) such that ax+by=gcd(x,y)
  if x < y:
    (a, b) = congruence(y, x)
    return (b, a)
  z = x % y
  if z == 0:
    return (0, 1)
  (c, d) = congruence(y, z)
  return (d, (c - int(x / y) * d) % 1000000007)

inverse_sum = {1: 1}
for i in range(2, 100000):
  inverse_sum[i] = (inverse_sum[i - 1] + congruence(1000000007, i)[1]) % 1000000007

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

N_factorial = 1
for i in range(1, N + 1):
  N_factorial = (N_factorial * i) % 1000000007

ans = 0
for i in range(N):
  ans = (ans + (inverse_sum[i + 1] + inverse_sum[N - i] - 1) * A[i] * N_factorial) % 1000000007

print(ans)

Fixed submission:
def congruence(x, y): #=(a, b) such that ax+by=gcd(x,y)
  if x < y:
    (a, b) = congruence(y, x)
    return (b, a)
  z = x % y
  if z == 0:
    return (0, 1)
  (c, d) = congruence(y, z)
  return (d, (c - int(x / y) * d) % 1000000007)

inverse_sum = {1: 1}
for i in range(2, 100001):
  inverse_sum[i] = (inverse_sum[i - 1] + congruence(1000000007, i)[1]) % 1000000007

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

N_factorial = 1
for i in range(1, N + 1):
  N_factorial = (N_factorial * i) % 1000000007

ans = 0
for i in range(N):
  ans = (ans + (inverse_sum[i + 1] + inverse_sum[N - i] - 1) * A[i] * N_factorial) % 1000000007

print(ans)
Buggy python submission (verdict: Runtime Error):
N = input()
A = []
for i in xrange(N):
	A.append(input())
ans = 0
start = 0
for i in xrange(N):
%	if A[i] > i - start:
	if A[i] > A[i-1] + 1:
		ans = -1
		break
	if i == 0:
		continue
	if A[i] == A[i - 1] + 1:
		ans += 1
		continue
	if A[i] == 0:
		start = i
		continue
	ans += A[i]
print ans



Fixed submission:
N = input()
A = []
for i in xrange(N):
	A.append(input())
ans = 0
start = 0
for i in xrange(N):
	if A[i] > i - start:
		ans = -1
		break
	if A[i] > A[i-1] + 1:
		ans = -1
		break
	if i == 0:
		continue
	if A[i] == A[i - 1] + 1:
		ans += 1
		continue
	if A[i] == 0:
		start = i
		continue
	ans += A[i]
print ans
Buggy python submission (verdict: Runtime Error):
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

void solve() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    sort(a.begin(), a.end());
    int n = a[N - 1], k = n / 2;
    cout << n << " ";
    auto i = lower_bound(a.begin(), a.end(), k);
    if (*(i + 1) - k < k - *i) cout << *(i + 1) << endl;
    else cout << *i << endl;
    return;
}

int main() {
    solve();
}

Fixed submission:
import bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = a[-1] / 2
i = bisect.bisect(a, b)
if a[i] - b < b - a[i - 1]:
    print(a[-1], a[i])
else:
    print(a[-1], a[i - 1])
Buggy python submission (verdict: Runtime Error):
R, C = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
    (y, x, z) = q.pop(0)
    for v, w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        t = x + v
        u = y + w
        if t < 0 or t >= C or u < 0 or u >= R:
            continue
        if c[u][t] == '.' and (u, t) not in d:
            q.append((u, t, z + 1))
            d[u, t] = z + 1
ans = R * C - d[R - 1, C - 1] - 1
for i in c:
    for j in i:
        if j == '#':
            ans -= 1
print(ans)

Fixed submission:
R, C = map(int, input().split())
c = [list(input()) for _ in range(R)]
d = {}
q = [(0, 0, 0)]
d[0, 0] = 0
while q != []:
    (y, x, z) = q.pop(0)
    for v, w in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        t = x + v
        u = y + w
        if t < 0 or t >= C or u < 0 or u >= R:
            continue
        if c[u][t] == '.' and (u, t) not in d:
            q.append((u, t, z + 1))
            d[u, t] = z + 1
if (R - 1, C - 1) not in d:
    ans = -1
else:
    ans = R * C - d[R - 1, C - 1] - 1
    for i in c:
        for j in i:
            if j == '#':
                ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)
#print(vs)
for i in range(4):
    vs[i].sort()
#print(vs)
ans = 0
for i in range(N + 1):
    if i * w1 > W:
        break
    if i == 0:
        si = 0
    else:
        si = sum(vs[0][-i:])
    for j in range(N + 1 - i):
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        if j > 0:
            sj += sum(vs[1][-j:])
        for k in range(N + 1 - i - j):
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            if k > 0:
                sk += sum(vs[2][-k:])
            for l in range(N + 1 - i - j - k):
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk               
                if l > 0:
                    sl += sum(vs[3][-l:])
                ans = max(ans, sl)
print(ans)

Fixed submission:
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)
#print(vs)
for i in range(4):
    vs[i].sort()
#print(vs)
ans = 0
for i in range(N + 1):
    if i * w1 > W:
        break
    if i == 0:
        si = 0
    else:
        si = sum(vs[0][-i:])
    for j in range(N + 1 - i):
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        if j > 0:
            sj += sum(vs[1][-j:])
        for k in range(N + 1 - i - j):
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            if k > 0:
                sk += sum(vs[2][-k:])
            for l in range(N + 1 - i - j - k):
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk               
                if l > 0:
                    sl += sum(vs[3][-l:])
                ans = max(ans, sl)
print(ans)
Buggy python submission (verdict: Runtime Error):
#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

const int MAX_N = 200001;
int par[MAX_N];
int rnk[MAX_N];

void init(int n) {
    rep(i,n) {
        par[i] = i;
        rnk[i] = 0;
    }
}

int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rnk[x] == rnk[y]) rnk[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void solve() {
    int N, K, L, p, q;
    cin >> N >> K >> L;
    init(N);
    rep(i,K) {
        cin >> p >> q;
        unite(p - 1, q - 1);
    }
    int roads[N];
    rep(i,N) roads[i] = find(i);
    init(N);
    rep(i,L) {
        cin >> p >> q;
        unite(p - 1, q - 1);
    }
    map<pair<int, int>, int> d;
    rep(i,N) d[make_pair(roads[i], find(i))]++;
    rep(i,N) cout << d[make_pair(roads[i], find(i))] << " ";
    cout << endl;
    return;
}

int main() {
    solve();
}

Fixed submission:
def init(par, n):
    global rank
    par = [i for i in range(n)]
    rank = [0] * n

def find(par, x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par, par[x])
        return par[x]

def unite(par, x, y):
    global rank
    x = find(par, x)
    y = find(par, y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

N, K, L = map(int, input().split())
roads = [i for i in range(N)]
rank = [0] * N
for i in range(K):
    p, q = map(int, input().split())
    unite(roads, p - 1, q - 1)
rails = [i for i in range(N)]
rank = [0] * N
for i in range(L):
    p, q = map(int, input().split())
    unite(rails, p - 1, q - 1)
d = {}
for i in range(N):
    d[find(roads, i), find(rails, i)] = d.get((find(roads, i), find(rails, i)), 0) + 1
for i in range(N):
    print(d[find(roads, i), find(rails, i)], end = " ")
print()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
c = [0, N + 1]
ans = 0
for i in range(1, N + 1):
    m = b[i]
    x = bisect.bisect(c, m)
    y = c[x - 1]
    z = c[x]
    ans += (((z - y) * (z - y - 1) - (m - y) * (m - y - 1) - (z - m) * (z - m - 1)) // 2) * i
    bisect.insort(c, m)
print(ans)

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]
ans = 0
for i in range(N, 0, -1):
    m = b[i]
    x = l[m]
    y = r[m]
    ans += (m - x + 1) * (y - m + 1) * i
    r[x - 1] = y
    l[y + 1] = x
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
a = list(zip(list(map(int, input().split())), range(1, N + 1)))
b = [0, N + 1]
a.sort()
ans = 0
for j, i in a:
    x = bisect.bisect(b, i)
    y = b[x - 1]
    z = b[x]
    ans += (((z - y) * (z - y - 1) - (i - y) * (i - y - 1) - (z - i) * (z - i - 1)) // 2) * j
    bisect.insort(b, i)
print(ans)

Fixed submission:
N = int(input())
a = list(map(int, input().split()))
b = [0] * (N + 1)
for i in range(N):
    b[a[i]] = i + 1
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]
ans = 0
for i in range(N, 0, -1):
    m = b[i]
    x = l[m]
    y = r[m]
    ans += (m - x + 1) * (y - m + 1) * i
    r[x - 1] = y
    l[y + 1] = x
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, N = map(int, input().split())
d = {}
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for i in range(N):
    a, b = map(int, input().split())
    for v in [a - 1, a, a + 1]:
        if v < 2 or v > H - 1:
            continue
        for w in [b - 1, b, b + 1]:
            if w < 2 or w > W - 1:
                continue
            black = 0
            for x in [v - 1, v, v + 1]:
                for y in [w - 1, w, w + 1]:
                    black += d.get((x, y), 0)
            ans[black] -= 1
            ans[black + 1] +=1
            #print(a, b, black, ans)
    d[a, b] = 1
    #print(d)
for i in ans:
    print(i)

Fixed submission:
H, W, N = map(int, input().split())
d = {}
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for i in range(N):
    a, b = map(int, input().split())
    for v in [a - 1, a, a + 1]:
        if v < 2 or v > H - 1:
            continue
        for w in [b - 1, b, b + 1]:
            if w < 2 or w > W - 1:
                continue
            black = 0
            for x in [v - 1, v, v + 1]:
                for y in [w - 1, w, w + 1]:
                    black += d.get((x, y), 0)
            ans[black] -= 1
            ans[black + 1] +=1
            #print(a, b, black, ans)
    d[a, b] = 1
    #print(d)
for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
N = int(input())
print(int(N * (N + 1) / 2)

Fixed submission:
N = int(input())
print(int(N * (N + 1) / 2))
Buggy python submission (verdict: Runtime Error):

import sys
input = sys.stdin.readline

n=input()

nn=0
for i in range(len(n)):
    nn+=int(n[i])

if nn%9==0:
    print("Yes")
else:
    print("No")
    

Fixed submission:
n=input()

nn=0
for i in range(len(n)):
    nn+=int(n[i])

if nn%9==0:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):

import sys
input = sys.stdin.readline

n=int(input())

def digsum(n):
    res = 0
    while n > 0 :
        res += n%10
 #       res +=1
        n =n// 10
    return res

nn=digsum(n)
if nn%9==0:
    print("Yes")
else:
    print("No")
    

Fixed submission:
n=input()

nn=0
for i in range(len(n)):
    nn+=int(n[i])

if nn%9==0:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):

n=int(input())

def digsum(n):
    res = 0
    while n > 0 :
        res += n%10
 #       res +=1
        n =n// 10
    return res

nn=digsum(n)
if nn%9==0:
    print("Yes")
else:
    print("No")
    

Fixed submission:
n=input()

nn=0
for i in range(len(n)):
    nn+=int(n[i])

if nn%9==0:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
h,w,m=map(int,input().split())
hw=[[0]*w for i in range(h)]
for i in range(m):
    hi,wi=map(int,input().split())
    hw[hi-1][wi-1]=1    

ws=[0]*h
for i in range(h):
    ws[i]=0
    for j in range(w):
        ws[i]+=hw[i][j]
hs=[0]*w
for j in range(w):
    hs[j]=0
    for i in range(h):
        hs[j]+=hw[i][j]
        
hwmax=0
for i in range(h):
    for j in range(w):
        if hw[i][j]==1:
            x=ws[i]+hs[j]-1
        else:
            x=ws[i]+hs[j]
#        print(i,j,x)
        hwmax=max(hwmax,x)
        
print(hwmax)
            


Fixed submission:

import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
hs=dict()
ws=dict()
hw=set()
for i in range(m):
    hi,wi=map(int,input().split())
    if hi-1 in ws:
        ws[hi-1]+=1
    else:
        ws[hi-1]=1
    if wi-1 in hs:
        hs[wi-1]+=1
    else:
        hs[wi-1]=1
    hw.add((hi-1,wi-1))    

wmax=max(list(ws.values()))
hh=[]
for ik,wv in ws.items():
    if wv==wmax:
        hh.append(ik)
hmax=max(list(hs.values()))
ww=[]
for jk,hv in hs.items():
    if hv==hmax:
        ww.append(jk)
        
for hi in hh:
    for wi in ww:
        if  not ((hi,wi) in hw):
#            print(hi,wi)
            print(wmax+hmax) 
            sys.exit()
print(wmax+hmax-1)

Buggy python submission (verdict: Runtime Error):

import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
hw=[[0]*w for i in range(h)]
for i in range(m):
    hi,wi=map(int,input().split())
    hw[hi-1][wi-1]=1    

ws=[0]*h
for i in range(h):
    ws[i]=0
    for j in range(w):
        ws[i]+=hw[i][j]
hs=[0]*w
for j in range(w):
    hs[j]=0
    for i in range(h):
        hs[j]+=hw[i][j]
        
hwmax=0
for i in range(h):
    for j in range(w):
        if hw[i][j]==1:
            x=ws[i]+hs[j]-1
        else:
            x=ws[i]+hs[j]
#        print(i,j,x)
        hwmax=max(hwmax,x)
        
print(hwmax)
            


Fixed submission:

import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
hs=dict()
ws=dict()
hw=set()
for i in range(m):
    hi,wi=map(int,input().split())
    if hi-1 in ws:
        ws[hi-1]+=1
    else:
        ws[hi-1]=1
    if wi-1 in hs:
        hs[wi-1]+=1
    else:
        hs[wi-1]=1
    hw.add((hi-1,wi-1))    

wmax=max(list(ws.values()))
hh=[]
for ik,wv in ws.items():
    if wv==wmax:
        hh.append(ik)
hmax=max(list(hs.values()))
ww=[]
for jk,hv in hs.items():
    if hv==hmax:
        ww.append(jk)
        
for hi in hh:
    for wi in ww:
        if  not ((hi,wi) in hw):
#            print(hi,wi)
            print(wmax+hmax) 
            sys.exit()
print(wmax+hmax-1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

nn=1000//100*2**(n//2+1)
dp=[[0]*nn for i in range(n)]

ni=1000//a[0]
for i in range(ni+1):    
    dp[0][i]=1000-a[0]*i

for k in range(1,n):
    for i in range(nn):
        xmax=0
        for ii in range(nn):
            x=dp[k-1][ii]+(ii-i)*a[k]
            if x<0:continue
            if dp[k-1][i]//a[k-1]<ii:break
            xmax=max(xmax,x) 
        dp[k][i]=xmax

print(dp[n-1][0])


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

dp=[[0]*2 for i in range(n)]
dk=[[0]*2 for i in range(n)]

#--------------- kabu=0
dp[0][0]=1000
dk[0][0]=0
#--------------- all kabu
dp[0][1]=1000%a[0]
dk[0][1]=1000//a[0]

for k in range(1,n):
    dp[k][0]=max(dp[k-1][0],dp[k-1][1]+dk[k-1][1]*a[k])
    dk[k][0]=0

    dpk1=dp[k-1][0]%a[k]
    dkk1=dp[k-1][0]//a[k]
    v1=dk[k-1][1]*a[k]+dp[k-1][1]
    v2=dkk1*a[k]+dpk1
#    if dkk1>dk[k-1][1]:
    if v2>v1:
        dk[k][1]=dkk1
        dp[k][1]=dpk1
    else:
        dp[k][1]=dp[k-1][1]
        dk[k][1]=dk[k-1][1]

print(dp[n-1][0])

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

nn=1000//100*2**(n//2+1)
dp=[[0]*nn for i in range(n)]

ni=1000//a[0]
for i in range(ni+1):    
    dp[0][i]=1000-a[0]*i

for k in range(1,n):
    for i in range(nn):
        xmax=0
        for ii in range(nn):
            x=dp[k-1][ii]+(ii-i)*a[k]
            if x<0:continue
            if dp[k-1][i]//a[k-1]<ii:break
            xmax=max(xmax,x) 
        dp[k][i]=xmax

print(dp[n-1][0])


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

dp=[[0]*2 for i in range(n)]
dk=[[0]*2 for i in range(n)]

#--------------- kabu=0
dp[0][0]=1000
dk[0][0]=0
#--------------- all kabu
dp[0][1]=1000%a[0]
dk[0][1]=1000//a[0]

for k in range(1,n):
    dp[k][0]=max(dp[k-1][0],dp[k-1][1]+dk[k-1][1]*a[k])
    dk[k][0]=0

    dpk1=dp[k-1][0]%a[k]
    dkk1=dp[k-1][0]//a[k]
    v1=dk[k-1][1]*a[k]+dp[k-1][1]
    v2=dkk1*a[k]+dpk1
#    if dkk1>dk[k-1][1]:
    if v2>v1:
        dk[k][1]=dkk1
        dp[k][1]=dpk1
    else:
        dp[k][1]=dp[k-1][1]
        dk[k][1]=dk[k-1][1]

print(dp[n-1][0])