Problem:


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]
hlist = [0]*h
wlist = [0]*w
for i in hw:
    hlist[i[0]-1]+=1
    wlist[i[1]-1]+=1

hmax=max(hlist) 
h_index = [n for n, v in enumerate(hlist) if v == hmax]
wmax=max(wlist)
w_index = [n for n, v in enumerate(wlist) if v == wmax]

count = sum(x-1 in h_index and y-1 in w_index for x,y in hw)
print(hmax+wmax-(count==len(h_index)*len(w_index)))

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H ={i:0 for i in range(1,H+1)}
bom_W ={i:0 for i in range(1,W+1)}
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]
temp_H =max_H[0][1]
temp_W =max_W[0][1]

ans =temp_H +temp_W -1
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==0:
            ans =v_h +v_w 
            print(ans)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
h_list = []
w_list = []
bomber = []
for _ in range(M):
    h, w = map(int, input().split())
    h_list.append(h)
    w_list.append(w)
    bomber.append([h, w])
h_cnt = Counter(h_list)
w_cnt = Counter(w_list)
ans = 0
for h_key, h_value in h_cnt.items():
    for w_key, w_value in w_cnt.items():
        tmp = 0
        if [h_key, w_key] in bomber:
            tmp -= 1
        ans = max(ans, h_value + w_value + tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    H, W, M = list(map(int, input().split()))
    HW = [list(map(int, input().split())) for _ in range(M)]
    rowsum = [0 for _ in range(H)]
    colsum = [0 for _ in range(W)]
    for h, w in HW:
        rowsum[h-1] += 1
        colsum[w-1] += 1
    rmax = 0
    ridx = []
    for i, r in enumerate(rowsum):
        if rmax < r:
            rmax = r
            ridx = [i]
        elif rmax == r:
            ridx.append(i)
    cmax = 0
    cidx = []
    for j, c in enumerate(colsum):
        if cmax < c:
            cmax = c
            cidx = [j]
        elif cmax == c:
            cidx.append(j)
    
    import itertools
    cnt = 0
    for h, w in HW:
        if h-1 in ridx and w-1 in cidx:
            cnt += 1
    
    print(rmax + cmax if cnt < len(cidx)*len(ridx) else rmax + cmax - 1)

    
    


if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
S = [tuple(map(int, input().split())) for _ in range(M)]

Y = [0] * H
X = [0] * W

for i in range(M):
    y, x = S[i]
    y, x = y-1, x-1
    Y[y] += 1
    X[x] += 1

YM = max(Y)
XM = max(X)

YI = []
for i in range(H):
    if Y[i] == YM:
        YI.append(i)

XI = []
for i in range(W):
    if X[i] == XM:
        XI.append(i)

for y in YI:
    for x in XI:
        if (y+1, x+1) not in S:
            print(YM+XM)
            exit()
else:
    print(YM+XM-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb=[]
x=[0]*(h+1)
y=[0]*(w+1)
for i in range(m):
    h1,w1=map(int,input().split())
    x[h1]+=1
    y[w1]+=1
    bomb.append((h1,w1))
maxx=max(x)
maxy=max(y)
r=[]
c=[]
for i in range(1,h+1):
    if x[i]==maxx:
        r.append(i)
for j in range(1,w+1):
    if y[j]==maxy:
        c.append(j)
for j in r:
    for k in c:
        if (j,k) not in bomb:
            print(maxx+maxy)
            exit()
print(maxx+maxy-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
g=[0]*h
l=[0]*w
b=[]
for i in range(m):
  x,y=map(int,input().split())
  g[x-1]+=1
  l[y-1]+=1
  b.append((x-1,y-1))
mxg=max(g);mxl=max(l)
mg=[i for i,x in enumerate(g) if x==mxg]
ml=[i for i,x in enumerate(l) if x==mxl]
c=0
for x,y in b:
  if x in mg and y in ml:
    c+=1
print(mxg+mxl-(c==(len(mg)*len(ml))))

Submission status: Time Limit Exceeded

Solution code:
import heapq
h, w, m = map(int, input().split())

M = [list(map(int, input().split())) for _ in range(m)]
hh = [0]*(h+1)
ww = [0]*(w+1)
check = [[False]*(w+1) for _ in range(h+1)]
for i in range(m):
    h, w = M[i][0], M[i][1]
    hh[h] += 1
    ww[w] += 1
    check[h][w] = True
nux = 0
hhh = []
www = []
for i, ph in enumerate(hh):
    heapq.heappush(hhh, [-ph, i])

for i, pw in enumerate(ww):
    heapq.heappush(www, [-pw, i])

mh = heapq.heappop(hhh)
mhl = [mh[1]]
for dh in hhh:
    if dh[0] == mh[0]:
        mhl.append(dh[1])
    else:
        break
mw = heapq.heappop(www)
mwl = [mw[1]]
for dw in www:
    if dw[0] == mw[0]:
        mwl.append(dw[1])
    else:
        break

for hl in mhl:
    for hw in mwl:
        if check[hl][hw] == False:
            print(-mw[0]-mh[0])
            exit()

print(-mw[0]-mh[0]-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb=[]
x=[0]*(h+1)
y=[0]*(w+1)
for i in range(m):
    h1,w1=map(int,input().split())
    x[h1]+=1
    y[w1]+=1
    bomb.append((h1,w1))
maxx=max(x)
maxy=max(y)
r=[]
c=[]
for i in range(1,h+1):
    if x[i]==maxx:
        r.append(i)
for j in range(1,w+1):
    if y[j]==maxy:
        c.append(j)
for j in r:
    for k in c:
        if not (j,k) in bomb:
            print(maxx+maxy)
            exit()
print(maxx+maxy-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

h, w, m = inpm()
rl = []
cl = []
for i in range(0, w):
    cl.append(0)
for i in range(0, h):
    rl.append(0)
maxr = 0
ri = []
maxc = 0
ci = []
l = []
for i in range(0, m):
    a , b = inpm()
    l.append([a- 1, b- 1])
    rl[a - 1] += 1
    cl[b - 1] += 1
    if(maxr < rl[a- 1]):
        maxr = rl[a- 1]
        ri.clear()
        ri.append(a- 1)
    elif(maxr == rl[a - 1]):
        ri.append(a- 1)
    if(maxc < cl[b- 1]):
        maxc = cl[b- 1]
        ci.clear()
        ci.append(b- 1)
    elif(maxc == cl[b - 1]):
        ci.append(b - 1)
ans = maxr + maxc
isSame = True
for r in ri:
    for c in ci:
        if(not [r, c] in l):
            isSame = False
            break
if(isSame):
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,m = map(int,input().split())
l = np.array([list(map(int, input().split())) for _ in range(m)])

gyo=np.array([0]*(h+1))
retu=np.array([0]*(w+1))
for i in range(m):
    gyo[l[i][0]]+=1
    retu[l[i][1]]+=1

max_gyo = np.array([i for i, x in enumerate(gyo) if x == max(gyo)])
max_retu = np.array([i for i, x in enumerate(retu) if x == max(retu)])

mark=0
for i in l:
    if i[0] in max_gyo and i[1] in max_retu:
        mark+=1

if len(max_gyo) * len(max_retu) - mark == 0:
    print(max(gyo)+max(retu)-1)
else:
    print(max(gyo)+max(retu))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from collections import Counter

H,W,M = map(int, input().split())
BH = [[0,i] for i in range(H)]
BW = [[0,i] for i in range(W)]
Bomb = set()
for _ in range(M):
  h,w = map(int, input().split())
  h,w = h-1,w-1
  BH[h][0] += 1
  BW[w][0] += 1
  Bomb.add((h,w))
  
BH.sort(reverse=True)
BW.sort(reverse=True)
  
"""
print(BombC)
print(BH)
print(BW)
"""

h = []
ans = 0
nowh, noww = 0,0
i,j = 0,0
BHMAX, BWMAX = BH[i][0], BW[j][0]
heapq.heappush(h, (-BH[i][0] - BW[j][0], BH[i][1], BW[j][1], i,j))
while h:
  cost, nowh, noww,i,j = heapq.heappop(h)
  cost = -cost
  #print(cost,nowh,noww)
  if (nowh,noww) not in Bomb:
    ans = max(ans,cost)
    break
  else:
    ans = max(ans, cost-1)
    if i+1 < H and BH[i+1][0] == BHMAX:
      heapq.heappush(h, (-BH[i+1][0] - BW[j][0], BH[i+1][1], BW[j][1],i+1, j))
    if j+1 < W and BW[i+1][0] == BWMAX:
      heapq.heappush(h, (-BH[i][0] - BW[j+1][0], BH[i][1], BW[j+1][1],i, j+1))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
l = [list(map(int, input().split())) for _ in range(m)]

gyo=[0]*(h+1)
retu=[0]*(w+1)
for i in range(m):
    gyo[l[i][0]]+=1
    retu[l[i][1]]+=1

max_gyo = [i for i, x in enumerate(gyo) if x == max(gyo)]
max_retu = [i for i, x in enumerate(retu) if x == max(retu)]

mark=0
for i in l:
    if i[0] in max_gyo and i[1] in max_retu:
        mark+=1

if len(max_gyo) * len(max_retu) - mark == 0:
    print(max(gyo)+max(retu)-1)
else:
    print(max(gyo)+max(retu))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit

@jit
def main():
    H, W, M = map(int, input().split())
    row = np.zeros(W)
    col = np.zeros(H)
    memo = []
    for _ in range(M):
        h, w = map(int, input().split())
        h -=1
        w -=1
        row[w] += 1
        col[h] += 1
        memo.append((h, w))

    col_max = col.max()
    row_max = row.max()

    max_col_indexs = np.where(col == col_max)[0]
    max_row_indexs = np.where(row == row_max)[0]

    ans = col_max + row_max -1
    for c in max_col_indexs:
        for r in max_row_indexs:
            if (c, r) not in memo:
                ans = ans = col_max + row_max
                break

    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from collections import Counter

H,W,M = map(int, input().split())
BH = [[0,i] for i in range(H)]
BW = [[0,i] for i in range(W)]
Bomb = set()
for _ in range(M):
  h,w = map(int, input().split())
  h,w = h-1,w-1
  BH[h][0] += 1
  BW[w][0] += 1
  Bomb.add((h,w))
  
BH.sort(reverse=True)
BW.sort(reverse=True)
  
"""
print(BombC)
print(BH)
print(BW)
"""

h = []
ans = 0
nowh, noww = 0,0
i,j = 0,0
heapq.heappush(h, (-BH[i][0] - BW[j][0], BH[i][1], BW[j][1], i,j))
while h:
  cost, nowh, noww,i,j = heapq.heappop(h)
  cost = -cost
  #print(cost,nowh,noww)
  if (nowh,noww) not in Bomb:
    ans = max(ans,cost)
    break
  else:
    ans = max(ans, cost-1)
    if i+1 < H:
      heapq.heappush(h, (-BH[i+1][0] - BW[j][0], BH[i+1][1], BW[j][1],i+1, j))
    if j+1 < W:
      heapq.heappush(h, (-BH[i][0] - BW[j+1][0], BH[i][1], BW[j+1][1],i, j+1))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from collections import Counter

H,W,M = map(int, input().split())
BH = [[0,i] for i in range(H)]
BW = [[0,i] for i in range(W)]
Bomb = []
for _ in range(M):
  h,w = map(int, input().split())
  h,w = h-1,w-1
  BH[h][0] += 1
  BW[w][0] += 1
  Bomb.append((h,w))
  
BH.sort(reverse=True)
BW.sort(reverse=True)
  
BombC = Counter(Bomb)
"""
print(BombC)
print(BH)
print(BW)
"""

h = []
ans = 0
nowh, noww = 0,0
i,j = 0,0
heapq.heappush(h, (-BH[i][0] - BW[j][0], BH[i][1], BW[j][1], i,j))
while h:
  cost, nowh, noww,i,j = heapq.heappop(h)
  cost = -cost
  #print(cost,nowh,noww)
  if (nowh,noww) not in BombC:
    ans = max(ans,cost)
    break
  else:
    ans = max(ans, cost-BombC[(nowh,noww)])
    if i+1 < H:
      heapq.heappush(h, (-BH[i+1][0] - BW[j][0], BH[i+1][1], BW[j][1],i+1, j))
    if j+1 < W:
      heapq.heappush(h, (-BH[i][0] - BW[j+1][0], BH[i][1], BW[j+1][1],i, j+1))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())

squares = []
for i in range(H):
    arr = []
    for j in range(W):
        arr.append(0)
    squares.append(arr)

boms = []
for i in range(M):
    hi, wi = map(int, input().split())
    squares[hi-1][wi-1] = 1
    boms.append([hi-1, wi-1])

row_sums = []
for i in range(H):
    row_sums.append(sum(squares[i]))

col_sums = []
for j in range(W):
    sum = 0
    for i in range(H):
        sum += squares[i][j]
    col_sums.append(sum)

row_max = max(row_sums)
col_max = max(col_sums)

row_hits = 0
for i in range(H):
    if row_sums[i] == row_max:
        row_hits += 1

col_hits = 0
for j in range(W):
    if col_sums[j] == col_max:
        col_hits += 1

hits = 0
for bom in boms:
    if row_sums[bom[0]] == row_max and col_sums[bom[1]] == col_max:
        hits += 1

if hits == row_hits * col_hits:
    print(row_max + col_max - 1)
else:
    print(row_max + col_max)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())

squares = []
for i in range(H):
    arr = []
    for j in range(W):
        arr.append(0)
    squares.append(arr)

boms = []
for i in range(M):
    hi, wi = map(int, input().split())
    squares[hi-1][wi-1] = 1
    boms.append([hi-1, wi-1])

row_sums = []
for i in range(H):
    row_sums.append(sum(squares[i]))

col_sums = []
for j in range(W):
    sum = 0
    for i in range(H):
        sum += squares[i][j]
    col_sums.append(sum)

row_max = max(row_sums)
col_max = max(col_sums)

row_indexes = []
for i in range(H):
    if row_sums[i] == row_max:
        row_indexes.append(i)

col_indexes = []
for j in range(W):
    if col_sums[j] == col_max:
        col_indexes.append(j)

hits = 0
for bom in boms:
    if bom[0] in row_indexes and bom[1] in col_indexes:
        hits += 1

if hits == len(row_indexes) * len(col_indexes):
    print(row_max + col_max - 1)
else:
    print(row_max + col_max)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W, M = map(int,input().split())

X = [0] * H
Y = [0] * W

A = []
m = M
while m:
    m -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    X[x] += 1
    Y[y] += 1
    
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = xm + ym - 1

bl = False
for i in xms:
    for j in yms:
        if not (i, j) in A:
            print(ans + 1)
            sys.exit()
            bl = True
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
HW = list(tuple(int(x) - 1 for x in input().split()) for _ in range(M))
h = [0] * H
w = [0] * W
for hi, wi in HW:
	h[hi] += 1
	w[wi] += 1
hm = max(h)
wm = max(w)

hh = [i for i, v in enumerate(h) if v == hm]
ww = [i for i, v in enumerate(w) if v == wm]

ans = hm + wm - 1
for h in hh:
	for w in ww:
		if (h, w) not in HW:
			ans += 1
			break 	
	else:
		continue
	break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())

squares = []
for i in range(H):
    arr = []
    for j in range(W):
        arr.append(0)
    squares.append(arr)

for i in range(M):
    hi, wi = map(int, input().split())
    squares[hi-1][wi-1] = 1

row_sums = []
for i in range(H):
    row_sums.append(sum(squares[i]))

col_sums = []
for j in range(W):
    sum = 0
    for i in range(H):
        sum += squares[i][j]
    col_sums.append(sum)

row_max = max(row_sums)
col_max = max(col_sums)

row_indexes = []
for i in range(H):
    if row_sums[i] == row_max:
        row_indexes.append(i)

col_indexes = []
for j in range(W):
    if col_sums[j] == col_max:
        col_indexes.append(j)

for i in row_indexes:
    for j in col_indexes:
        if squares[i][j] == 0:
            print(row_max + col_max)
            exit()

print(row_max + col_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
l = [list(map(int, input().split())) for _ in range(m)]

gyo=[0]*(h+1)
for i in range(m):
    gyo[l[i][0]]+=1

max_gyo = [i for i, x in enumerate(gyo) if x == max(gyo)]

retu=[0]*(w+1)
for i in range(m):
    retu[l[i][1]]+=1

max_retu = [i for i, x in enumerate(retu) if x == max(retu)]

mark=1
for i in max_gyo:
    for j in max_retu:
        if [i,j] not in l:
            mark=0
            break
    break

if mark==1:
    print(max(gyo)+max(retu)-1)
else:
    print(max(gyo)+max(retu))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W,M=map(int,input().split())
bom = [] #ボムの場所
bomH =[0]*(H+1) 
bomW=[0]*(W+1)

for _ in range(M):
    h,w=map(int,input().split())
    bom.append((h,w))
    bomH[h]+=1
    bomW[w]+=1

#縦の爆弾と横の爆弾は独立。爆弾を置く場所に爆弾があると-1
max_bomH = max(bomH)
max_bomW = max(bomW)

index_max_H = []
index_max_W = []

for ih in range(H+1):
    if bomH[ih] == max_bomH:
        index_max_H.append(ih)

for iw in range(W+1):
    if bomW[iw] == max_bomW:
        index_max_W.append(iw)

point = itertools.product(index_max_H,index_max_W)#置き場所候補
sPoint = set(point)
sBom = set(bom)
#爆弾が置き場所候補から爆弾場所を消す,すべてなくなれば、-1,どこか残れば0
for sb in sBom:
    sPoint.discard(sb)

print(max_bomH+max_bomW - (len(sPoint)==0) )

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

g = [[False] * W for _ in range(H)]

for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    g[Th - 1][Tw - 1] = True

ans = max(h) + max(w)

index_h = [n for n, v in enumerate(h) if v == max(h)]
index_w = [n for n, v in enumerate(w) if v == max(w)]

sub = 1
for ih in index_h:
    for iv in index_w:
        if g[ih][iv] is False:
            sub = 0
            break
    else:
        continue
    break

ans -= sub


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
A=[]
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

add=1
A.sort()
for i in mh:
    for j in mw:
        #print(hs[i],ws[j])
        a=0
        for k in range(len(A)):
            if A[k]==(i,j):
                a=1
                A.remove((i,j))
                break
        if a==0:    
            add=0
            break
    if add==0:break

ans-=add

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
data = [[False]*(W+1) for i in range(H+1)]
 
for i in range(M):
    h,w = map(int,readline().split())
    data[h][w] = True
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
maxh = max(h_cnt)
maxw = max(w_cnt)
maxhInd = []
maxwInd = []
maxhInd = [i for i,a in enumerate(h_cnt) if a == maxh]
maxwInd = [i for i,a in enumerate(w_cnt) if a == maxw]
maxhCnt = len(maxhInd)
maxwCnt = len(maxwInd)

ans = maxh+maxw

if maxhCnt * maxwCnt > M:
    print(ans)
else:
    t = list(itertools.product(maxhInd, maxwInd))
    for h,w in t:
        if data[h][w] == False:
            print(ans)
            sys.exit()
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
A=[]
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

add=1
A.sort()
for i in mh:
    for j in mw:
        #print(hs[i],ws[j])
        if (i,j) in A:
            A.remove((i,j))
        else:
            add=0
            break
    if add==0:break

ans-=add

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys


H, W, M = map(int, input().split())
X = [set() for _ in range(H)]
Y = [set() for _ in range(W)]
for s in sys.stdin.readlines():
    h, w = map(lambda x: int(x) - 1, s.split())
    X[h].add(w)
    Y[w].add(h)
cntX = []
cntY = []
for x in X:
    cntX.append((len(x), x))
for w, y in enumerate(Y):
    cntY.append((len(y), w))

cntX.sort(reverse=True)
cntY.sort(reverse=True)
maxX = cntX[0][0]
maxY = cntY[0][0]
ans = 0
for cnt, x in cntX:
    if cnt < maxX:
        break
    for tmp, w in cntY:
        if tmp < maxY:
            break
        tmp += cnt - (w in x)
        if ans < tmp:
            ans = tmp
    if cnt == maxX + maxY:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
A=[]
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

add=1
for i in mh:
    for j in mw:
        #print(hs[i],ws[j])
        if (i,j) in A:
            A.remove((i,j))
        else:
            add=0
            break
    if add==0:break

ans-=add

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys


H, W, M = map(int, input().split())
X = [set() for _ in range(H)]
Y = [set() for _ in range(W)]
cntX = [0] * H
cntY = [0] * W
for s in sys.stdin.readlines():
    h, w = map(lambda x: int(x) - 1, s.split())
    X[h].add(w)
    Y[w].add(h)
    cntX[h] += 1
    cntY[w] += 1

maxX = max(cntX)
maxY = max(cntY)
ans = 0
if maxX > maxY:
    for i, cnt in enumerate(cntX):
        if cnt < maxX:
            continue
        for w in range(W):
            tmp = cnt + len(Y[w]) - (w in X[i])
            if ans < tmp:
                ans = tmp
else:
    for i, cnt in enumerate(cntY):
        if cnt < maxY:
            continue
        for h in range(H):
            tmp = cnt + len(X[h]) - (h in Y[i])
            if ans < tmp:
                ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
import sys


H, W, M = map(int, input().split())
X = [set() for _ in range(H)]
Y = [set() for _ in range(W)]
for s in sys.stdin.readlines():
    h, w = map(lambda x: int(x) - 1, s.split())
    X[h].add(w)
    Y[w].add(h)
cntX = []
cntY = []
for x in X:
    cntX.append((len(x), x))
for y in Y:
    cntY.append((len(y), y))

cntX.sort(reverse=True)
maxX = cntX[0][0]
ans = 0
for cnt, x in cntX:
    if cnt < maxX:
        break
    for w in range(W):
        tmp = cnt + len(Y[w]) - (w in x)
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

HMAXES = []
WMAXES = []
answer = 0
HMAX = max(H)
WMAX = max(W)


HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

HMAXES = []
WMAXES = []
answer = 0
HMAX = max(H)
WMAX = max(W)


# 3*10^5
for i, h in enumerate(H):
    if h == HMAX:
        HMAXES.append(i)
for i, w in enumerate(W):
    if w == WMAX:
        WMAXES.append(i)
# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

HMAXES = []
WMAXES = []
answer = 0
HMAX = max(H)
WMAX = max(W)


# 3*10^5
for i, h in enumerate(H):
    if h == HMAX:
        HMAXES.append(i)
for i, w in enumerate(W):
    if w == WMAX:
        WMAXES.append(i)
# 3*10^5
answer = HMAX + WMAX
for i, h in enumerate(HMAXES):
    for j, w in enumerate(WMAXES):
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

gh = {i:{} for i in range(h)}
gw = {i:{} for i in range(w)}

for _h, _w in hw:
    gh[_h-1][_w-1]=_w-1
    gw[_w-1][_h-1]=_h-1
    
ansh = 0
posh = {}
answ = 0
posw = {}
for k,v in gh.items():
    if len(v) > ansh:
        ansh = len(v)
        
for k,v in gh.items():
    if len(v) == ansh:
        posh[k]=k
        
for k,v in gw.items():
    if len(v) > answ:
        answ = len(v)
        
for k,v in gw.items():
    if len(v) == answ:
        posw[k]=k
        
hoge = True
for i in posh:
    for j in posw:
        if i not in gw[j]:
            hoge = False
            
if hoge:
    print(ansh+answ-1)
else:
    print(ansh+answ)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

gh = {i:[] for i in range(h)}
gw = {i:[] for i in range(w)}

for _h, _w in hw:
    gh[_h-1].append(_w-1)
    gw[_w-1].append(_h-1)
    
ansh = 0
posh = {}
answ = 0
posw = {}
for k,v in gh.items():
    if len(v) > ansh:
        ansh = len(v)
        
for k,v in gh.items():
    if len(v) == ansh:
        posh[k]=k
        
for k,v in gw.items():
    if len(v) > answ:
        answ = len(v)
        
for k,v in gw.items():
    if len(v) == answ:
        posw[k]=k
        
hoge = True
for i in posh:
    for j in posw:
        if i not in gw[j]:
            hoge = False
            
if hoge:
    print(ansh+answ-1)
else:
    print(ansh+answ)

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.readline

h, w, m = map(int, input().split())
t = []
for _ in range(m):
	a, b = map(int, input().split())
	t.append((a-1, b-1))
hor, ver = [0]*w, [0]*h
for i in range(h):
	for j in range(m):
		if i == t[j][0]: ver[i] += 1
for i in range(w):
	for j in range(m):
		if i == t[j][1]: hor[i] += 1

ans = 0
for i in range(h):
	for j in range(w):
		m = -1 if (i, j) in t else 0
		ans = max(ans, hor[j]+ver[i]+m)
print(ans)