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:
import sys


def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    # H, W, M = 3, 3, 3
    # targets = ((1, 1), (2, 1), (1, 3))
    
    target_h = [0] * H
    target_w = [0] * W
    target_hw = set()
    for h, w in targets:
        target_h[h - 1] += 1
        target_w[w - 1] += 1
        target_hw.add((h - 1, w - 1))

    ans = 0
    for h, a in enumerate(target_h):
        if a:
            for w, b in enumerate(target_w):
                if b:
                    ans = max(ans, target_h[h] + target_w[w] - (1 if (h, w) in target_hw else 0))
    
    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
dh = [0]*(h+1)
dw = [0]*(w+1)
l=[[0 for i in range(w+1)] for j in range(h+1)]
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[x][y]=1
m = 0
for i in range(1,h+1):
    if dh[i]>m:
        m = dh[i]
        hi=i
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[hi][i]==1:
        d-=1
    m = max(m,d)
c+=m
print(c)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
dh = [0]*(h+1)
dw = [0]*(w+1)
l=[[0 for i in range(w+1)] for j in range(h+1)]
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[x][y]=1
m = max(dh)
hi = dh.index(m)
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[hi][i]==1:
        d-=1
    m = max(m,d)
c+=m
print(c)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
dh = [0]*(h+1)
dw = [0]*(w+1)
l=[]
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l.append((x,y))
m = max(dh)
hi = dh.index(m)
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if (hi,i) in l:
        d-=1
    m = max(m,d)
c+=m
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
H,W,M=map(int,input().split())

X=[]
Y=[]
tt=[]
for i in range(M):
    inp=list(map(int,input().split()))
    X.append(inp[0])
    Y.append(inp[1])
    tt.append((inp[0],inp[1]))
Z1=Counter(X)
Z2=Counter(Y)
maxmax=0
for i in Z1.keys():
    for j in Z2.keys():
        aa=0
        if (i,j) in tt:
            aa=-1
        if maxmax<(aa+Z1[i]+Z2[j]):
            maxmax=(aa+Z1[i]+Z2[j])
print(maxmax)

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w, m = map(int, input().split())
x = []
y = []
bomb = []
for i in range(m):
  tmp_x, tmp_y = map(int, input().split())
  x.append(tmp_x)
  y.append(tmp_y)
  bomb.append([tmp_x, tmp_y])

c_x = collections.Counter(x)
c_y = collections.Counter(y)
_max_x = c_x.most_common()[0][1]
_max_y = c_y.most_common()[0][1]

count = 0
for i in bomb:
  if c_x[i[0]] == _max_x and c_y[i[1]] == _max_y:
    count += 1

if count == len([kv[0] for kv in c_x.items() if kv[1] == max(c_x.values())]) * len([kv[0] for kv in c_y.items() if kv[1] == max(c_y.values())]):
  print(_max_x + _max_y - 1)
else:
  print(_max_x + _max_y)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


H, W, M = zz()
target_h = [0]*M
target_w = [0] * M
target_table = [[0]*W for _ in range(H)]
for i in range(M):
    h, w = zz()
    target_h[i] = h-1
    target_w[i] = w-1
    target_table[h-1][w-1] = 1

count_h = collections.Counter(target_h)
count_w = collections.Counter(target_w)

pos_h, num_max_h = count_h.most_common()[0]
pos_w, num_max_w = count_w.most_common()[0]
ans = num_max_h + num_max_w
muinus_one_flg = True
for pos_h, num_h in count_h.most_common():
    if (num_h != num_max_h):
        break
    for pos_w, num_w in count_w.most_common():
        if (num_w != num_max_w):
            break
        if (target_table[pos_h][pos_w] == 0):
            muinus_one_flg = False
if (muinus_one_flg):
    ans -= 1
print(ans)

# print('pos_h', 'pos_w', pos_h, pos_w)
# print('num_h', 'num_w', num_h, num_w)
# for pos_h, pos_w in zip(target_h, target_w):
#     if (count_h[pos_h] == num_h and count_w[pos_w] == num_w):

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
import numpy as np
from  collections import Counter
 
hw = [[0]*2 for _ in range(M)]
for _ in range(M):
  h, w = map(int, input().split())
  hw[_][0] = h
  hw[_][1] = w
  
#print(hw, hw[:, 0])
c_h = Counter([ i[0] for i in hw ]).most_common()
c_w = Counter([ i[1] for i in hw ]).most_common()

 
max_ch = c_h[0][1]
max_ch_lst = []
for _c_h in c_h:
  if _c_h[1] == max_ch:
    max_ch_lst.append(_c_h[0])
  else:
    break
    
max_cw = c_w[0][1]
max_cw_lst = []
for _c_w in c_w:
  if _c_w[1] == max_cw:
    max_cw_lst.append(_c_w[0])
  else:
    break

#print(max_ch_lst, max_cw_lst, hw)

flg = 1
for h in max_ch_lst:
  for w in max_cw_lst:
    if [h, w] not in hw:
      flg = 0
      break

print(max_ch + max_cw - flg)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in hlist:
    for j in wlist:
        flag=0
        for k in range(M):
            if (i+1)==l[k][0] and (j+1)==l[k][1]:
                flag=1
                break
        if flag==0:
            print(maxh+maxw)
            c=1
            break
    if c==1:
        break
if c==0:
    print(maxh+maxw-1)

Submission status: Time Limit Exceeded

Solution code:

H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in hlist:
    for j in wlist:
        flag=0
        for k in range(M):
            if (i+1)==l[k][0] and (j+1)==l[k][1]:
                flag=1
                break
        if flag==0:
            print(maxh+maxw)
            c=1
            break
    if c==1:
        break
if c==0:
    print(maxh+maxw-1)

Submission status: Time Limit Exceeded

Solution code:
def bomber(H, W, M, targets)-> int:
  result = 0
  for h in range(1, H+1):
    for w in range(1, W+1):
      result_temp = 0
      for m in range(M):
        if h == targets[m][0] or w == targets[m][1]:
          result_temp += 1
      if result_temp > result:
        result = result_temp
  return result

if __name__ == "__main__":
  hwm = list(map(int, input().split()))
  targets = [list(map(int, input().split())) for _ in range(hwm[2])]
  print(bomber(hwm[0], hwm[1], hwm[2], targets))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
 
h = [0] * H
w = [0] * W
Mem = [tuple(map(int, input().split())) for _ in range(M) ]
for i, j in Mem:
  h[i-1] += 1
  w[j-1] += 1

maxh = max(h)
maxw = max(w)
 
listh = [i for i, v in enumerate(h, 1) if v == maxh]
listw = [j for j, v in enumerate(w, 1) if v == maxw]

cnt = len(listh) * len(listw)

for i, j in Mem:
  if i in listh and j in listw:
    cnt -= 1
 
if cnt:
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
 
h = [0] * H
w = [0] * W
Mem = []
for _ in range(M):
  i, j = map(int, input().split())
  Mem += [(i, j)]
  h[i-1] += 1
  w[j-1] += 1

maxh = max(h)
maxw = max(w)
 
listh = [i for i, v in enumerate(h, 1) if v == maxh]
listw = [j for j, v in enumerate(w, 1) if v == maxw]

cnt = len(listh) * len(listw)

for i, j in Mem:
  if i in listh and j in listw:
    cnt -= 1
 
if cnt:
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W,M = input().split()
A = []
S = 0
for i in range(int(M)):
    a_ = input().split()
    a = [int(i)-1 for i in a_]
    A.append(a)
A = np.array(A)
h_ = A[:,0]
w_ = range(int(W))

for i in h_:
    for j in w_:
        s = sum(A[: , 0]==i) + sum(A[: , 1]==j) 
        if any([all(a ==np.array([i,j])) for a in A ]):
            s -=1
        if s > S:
            S =s

print(S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W,M = input().split()
A = []
S = 0
for i in range(int(M)):
    a_ = input().split()
    a = [int(i)-1 for i in a_]
    A.append(a)
A = np.array(A)
h_ = A[:,0]
w_ = range(int(W))

for i in h_:
    for j in w_:
        s = sum(A[: , 0]==i) + sum(A[: , 1]==j) 
        if any([all(a ==np.array([i,j])) for a in A ]):
            s -=1
        if s > S:
            S =s

print(S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W,M = input().split()
A = []
S = 0
for i in range(int(M)):
    a_ = input().split()
    a = [int(i)-1 for i in a_]
    A.append(a)
A = np.array(A)
h_ = range(int(H))
w_ = range(int(W))

for i in h_:
    for j in w_:
        s = sum(A[: , 0]==i) + sum(A[: , 1]==j) 
        if any([all(a ==np.array([i,j])) for a in A ]):
            s -=1
        if s > S:
            S =s

print(S)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
hrz = [0]*H
vrt = [0]*W
targets = set()
for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    targets.add((h, w))
    hrz[h] += 1
    vrt[w] += 1

hrz_max = max(hrz)
vrt_max = max(vrt)
for h in [i for i in range(H) if hrz[i] == hrz_max]:
    for w in [i for i in range(W) if vrt[i] == vrt_max]:
        if not (h, w) in targets:
            print(hrz_max+vrt_max)
            exit()
print(hrz_max+vrt_max-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().strip().split(" "))

row = [0]*h
col = [0]*w
bombs = {}
for i in range(m):
    x,y = map(int,input().strip().split(" "))
    ky = str(x-1)+'-'+str(y-1)
    bombs[ky] = 1
    row[x-1] += 1
    col[y-1] += 1

mr = max(row)
mri = []
for i in range(h):
    if row[i]==mr:
        mri.append(i)

mc = max(col)
mci = []
for i in range(w):
    if col[i]==mc:
        mci.append(i)

fans = 0
for i in range(len(mri)):
    for j in range(len(mci)):
        ans = row[mri[i]] + col[mci[j]] - 1
        ky = str(mri[i])+'-'+str(mci[j])
        if bombs.get(ky) is None:
            ans = ans + 1

        fans= max(ans, fans)
        
print(fans)

Submission status: Time Limit Exceeded

Solution code:

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

HSum=[0 for _ in range(H)]
WSum=[0 for _ in range(W)]


bombs = set()
for _ in range(M):
	hi,wi = map(lambda x:int(x)-1,input().split())
	HSum[hi] += 1
	WSum[wi] += 1
	bombs.add( (hi,wi) )
# print(HSum)
# print(WSum)



curMax = 0

## 計算量多すぎ。。
# for h in range(H):
# 	for w in range(W):
# 		tmp = HSum[h] + WSum[w]
# 		if curMax <= tmp:
# 			if (h,w) in bombs:
# 				tmp -= 1
# 			curMax = max( curMax, tmp )

hMax = max(HSum)
wMax = max(WSum)
tmpMax = hMax + wMax

ans = 0

# hSumMaxOnly = [h for h, x in enumerate(HSum) if x == hMax]
# wSumMaxOnly = [w for w, y in enumerate(WSum) if y == wMax]

for h in [h for h, x in enumerate(HSum) if x == hMax]:
	if ans == tmpMax:
		break
	for w in [w for w, y in enumerate(WSum) if y == wMax]:
		if (h,w) in bombs:
			ans = tmpMax - 1
		else:
			ans = tmpMax
			break



print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

HSum=[0 for _ in range(H)]
WSum=[0 for _ in range(W)]


bombs = []
for _ in range(M):
	hi,wi = map(lambda x:int(x)-1,input().split())
	HSum[hi] += 1
	WSum[wi] += 1
	bombs.append( (hi,wi) )
# print(HSum)
# print(WSum)



curMax = 0

## 計算量多すぎ。。
# for h in range(H):
# 	for w in range(W):
# 		tmp = HSum[h] + WSum[w]
# 		if curMax <= tmp:
# 			if (h,w) in bombs:
# 				tmp -= 1
# 			curMax = max( curMax, tmp )

hMax = max(HSum)
wMax = max(WSum)
tmpMax = hMax + wMax

ans = 0

# hSumMaxOnly = [h for h, x in enumerate(HSum) if x == hMax]
# wSumMaxOnly = [w for w, y in enumerate(WSum) if y == wMax]

for h in [h for h, x in enumerate(HSum) if x == hMax]:
	if ans == tmpMax:
		break
	for w in [w for w, y in enumerate(WSum) if y == wMax]:
		if (h,w) in bombs:
			ans = tmpMax - 1
		else:
			ans = tmpMax
			break



print(ans)

Submission status: Time Limit Exceeded

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

h_cnt = [0] * H
w_cnt = [0] * W
hw = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
for h, w in hw:
    h_cnt[h] += 1
    w_cnt[w] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

cnt = 0
for h, w in hw:
    if h in hs and w in ws:
        cnt += 1
if cnt < len(hs)*len(ws):
    print(max_h+max_w)
else:
    print(max_h+max_w-1)

Submission status: Time Limit Exceeded

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

h_cnt = [0] * H
w_cnt = [0] * W
hw = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
for h, w in hw:
    h_cnt[h] += 1
    w_cnt[w] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

cnt = 0
for h, w in hw:
    if h in hs and w in ws:
        cnt += 1
if cnt < len(hs)*len(ws):
    print(max_h+max_w)
else:
    print(max_h+max_w-1)

Submission status: Time Limit Exceeded

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

h_cnt = [0] * H
w_cnt = [0] * W
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append((h-1, w-1))
    h_cnt[h-1] += 1
    w_cnt[w-1] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

cnt = 0
for h, w in hw:
    if h in hs and w in ws:
        cnt += 1
if cnt < len(hs)*len(ws):
    print(max_h+max_w)
else:
    print(max_h+max_w-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

h_cnt = [0] * H
w_cnt = [0] * W
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append((h-1, w-1))
    h_cnt[h-1] += 1
    w_cnt[w-1] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = []
ws = []
for h in range(H):
    if h_cnt[h] == max_h:
        hs.append(h)
for w in range(W):
    if w_cnt[w] == max_w:
        ws.append(w)

cnt = 0
for h, w in hw:
    if h in hs and w in ws:
        cnt += 1
if cnt < len(hs)*len(ws):
    print(max_h+max_w)
else:
    print(max_h+max_w-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
nh=[0]*H
nw=[0]*W
boms=[]
for _ in range(H):
    boms.append([False]*W)
for _ in range(M):
    h,w=map(int,input().split())
    nh[h-1] += 1
    nw[w-1] += 1
    boms[h-1][w-1]=True

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if not boms[i][j]:
            print(maxh + maxw)
            exit()
print(maxh + maxw - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
x = []
max_a = 0
max_b = 0
a = []
b = []
for _ in range(m):
    x.append(input().split())

for i in range(h):
    cnt_a = 0
    for j in range(m):
        if str(i+1) == x[j][0]:
            cnt_a += 1
    if max_a < cnt_a:
        max_a = cnt_a
        a.clear()
        a.append(i+1)
    elif max_a == cnt_a:
        a.append(i+1)

for i in range(w):
    cnt_b = 0
    for j in range(m):
        if str(i+1) == x[j][1]:
            cnt_b += 1
    if max_b < cnt_b:
        max_b = cnt_b
        b.clear()
        b.append(i+1)
    elif max_b == cnt_b:
        b.append(i+1)

for i in a:
    for j in b:
        xx = [str(i), str(j)]
        if xx not in x:
            print(int(max_a) + int(max_b))
            exit()
else:
    print(int(max_a) + int(max_b) - 1)

Submission status: Time Limit Exceeded

Solution code:
########### E
H, W, M = map(int, input().split())
bombs = []
for _ in range(M):
    bomb = list(map(lambda x:int(x)-1, input().split()))
    bombs.append(bomb)

H_list = [0]*H
W_list = [0]*W
sign = True
for h,w in bombs:
    H_list[h] += 1
    W_list[w] += 1

max_H = [i for i,k in enumerate(H_list) if k == max(H_list)]
max_W = [i for i,k in enumerate(W_list) if k == max(W_list)]

cross = []

for i in max_H:
    for k in max_W:
        if [i,k] not in bombs:
            sign = False
            print(max(H_list) + max(W_list))
            break
    break

if sign:
    print(max(H_list) + max(W_list) -1)

Submission status: Time Limit Exceeded

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

Hmax_temp = [0]*(H+1)
Wmax_temp = [0]*(W+1)
Hmax = 0
Wmax = 0
for i in range(M):
	H_M,W_M = map(int,input().split())
	Hmax_temp[H_M] += 1
	Wmax_temp[W_M] += 1
	HW.append([H_M,W_M])

Hmax = max(Hmax_temp)
Wmax = max(Wmax_temp)

#H方向の走査
y_max = []
for i in range(H+1):
	if Hmax == Hmax_temp[i]:
		y_max.append(i)
		
#W方向の走査
x_max = []
for j in range(W+1):
	if Wmax == Wmax_temp[j]:
		x_max.append(j)

#爆弾設置位置に対象が存在するか？
flag = False
for i in y_max:
	for  j in x_max:
		if [i,j] not in HW:
			flag = True
			break
	if flag:
		break

#答えのセット
if flag:
	ans = Wmax + Hmax
else:
	ans = Wmax + Hmax - 1
print(ans)

Submission status: Time Limit Exceeded

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

L = [0]*H
R = [0]*W

li = []
s = []
t = []
ans = 0

for i in range(M):
    h, w = map(int, input().split())
    L[h-1] += 1
    R[w-1] += 1
    li.append((h-1, w-1))

lm = max(L)
rm = max(R)

ans = lm+rm-1
judge = False

for i, l in enumerate(L):
    if l == lm:
        s.append(i)
for j, r in enumerate(R):
    if rm == r:
        t.append(j)

for i in s:
    for j in t:
        if (i, j) not in li:
            ans = rm+lm
            judge = True
    if judge:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
H, W, M = map(int, input().split())
dich = defaultdict(list)
dicw = defaultdict(list)
hw = []
hwhw = []

for i in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])
    hwhw.append(str(h)+"#"+str(w))
    dich[h].append(w)
    dicw[w].append(h)

mh = 0
for k in dich:
    mh = max(mh, len(dich[k]))
    
mw= 0
for k in dicw:
    mw = max(mw, len(dicw[k]))
    
hl = []
for i in hw:
    if len(dich[i[0]])==mh:
        hl.append(i[0])
hl =set(hl)

wl = []
for i in hw:
    if len(dicw[i[1]])==mw:
        wl.append(i[1])
wl = set(wl)

cro = []
for i in hl:
    for j in wl:
        cro.append(str(i)+"#"+str(j))
cro = set(cro)
hwhw = set(hwhw)

if cro&hwhw==cro:
    print(mh+mw-1) 
else:
    print(mh+mw)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = []

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b.append((tmp[0], tmp[1]))

t = max(hallline)
s = max(wallline)

for i in (i for i in range(H) if hallline[i] == t):
    for j in (i for i in range(W) if wallline[i] == s):
        if (i, j) not in b:
            print(t + s)
            exit()
print(t + s - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
b = []

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b.append((tmp[0], tmp[1]))

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

for i in a:
    for j in c:
        if (i, j) not in b:
            print(t + s)
            exit()
print(t + s - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
for j in range(W):
    wallline[j] = 0
b = [[False for j in range(W)] for i in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline)
s = max(wallline)

a = [i for i in range(H) if hallline[i] == t]
c = [i for i in range(W) if wallline[i] == s]

for i in a:
    for j in c:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
H, W, M = map(int, input().split())
dich = defaultdict(list)
dicw = defaultdict(list)
hw = []

for i in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])
    dich[h].append(w)
    dicw[w].append(h)
#print(dich)
#print(dicw)
    
mh = 0
for k in dich:
    mh = max(mh, len(dich[k]))
    
mw= 0
for k in dicw:
    mw = max(mw, len(dicw[k]))
    
hl = []
for i in hw:
    if len(dich[i[0]])==mh:
        hl.append(i[0])
hl =set(hl)

wl = []
for i in hw:
    if len(dicw[i[1]])==mw:
        wl.append(i[1])
wl = set(wl)

for i in hl:
    for j in wl:
        if j in dich[i]:
            continue
        print(mh+mw) 
        sys.exit()
print(mh+mw-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hallline = [0 for i in range(H)]
wallline = [0 for i in range(W)]
for j in range(W):
    wallline[j] = 0
b = [[False for i in range(W)] for j in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline)
s = max(wallline)

hkeys = [i for i in range(H) if hallline[i] == t]
wkeys = [i for i in range(W) if wallline[i] == s]

for i in hkeys:
    for j in wkeys:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)

Submission status: Time Limit Exceeded

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

targets = []
rowsum = [0] * h
rowmax = 0
colsum = [0] * w
colmax = 0
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    targets.append((hi, wi))
    rowsum[hi] += 1
    rowmax = max(rowmax, rowsum[hi])
    colsum[wi] += 1
    colmax = max(colmax, colsum[wi])

rowindices = []
for i, v in enumerate(rowsum):
    if v == rowmax:
        rowindices.append(i)

colindices = []
for i, v in enumerate(colsum):
    if v == colmax:
        colindices.append(i)

ans = rowmax + colmax - 1
for ri in rowindices:
    for ci in colindices:
        if (ri, ci) not in targets:
            print(rowmax + colmax)
            exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def solve(H, M, W, bombs):
    count_h = defaultdict(int)
    count_w = defaultdict(int)
    for b in bombs:
        h = str(b[0])
        count_h[h] += 1
        w = str(b[1])
        count_w[w] += 1
    max_h = max(count_h.values())
    max_w = max(count_w.values())
    points_h = [int(k) for k in count_h.keys() if count_h[k] == max_h]
    points_w = [int(k) for k in count_w.keys() if count_w[k] == max_w]
    ans = max_h + max_w
    if _find_cross_bomb(points_h, points_w, bombs):
        ans -= 1
    print(ans)


def _find_cross_bomb(points_h, points_w, bombs):
    c = 0
    for b in bombs:
        if (b[0]) in points_h:
            if (b[1]) in points_w:
                c += 1
    return c == len(points_h) * len(points_w)


if __name__ == "__main__":
    H, W, M = map(int, input().split())
    bombs = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
    solve(H, M, W, bombs)

Submission status: Time Limit Exceeded

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

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

hor = [0] * H
ver = [0] * W
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hs = []
hmax = max(hor)
for i, v in enumerate(hor):
    if hmax == v:
        hs.append(i)
vs = []
vmax = max(ver)
for i, v in enumerate(ver):
    if vmax == v:
        vs.append(i)

ans = hmax + vmax

if len(hs) * len(vs) > m:
    print(ans)
    exit()

for k1 in hs:
    for k2 in vs:
        if f[k1][k2] == 0:
            print(ans)
            exit()
print(ans - 1)

Submission status: Time Limit Exceeded

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

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

hor = [0] * H
ver = [0] * W
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hs = []
hmax = max(hor)
for i, v in enumerate(hor):
    if hmax == v:
        hs.append(i)
vs = []
vmax = max(ver)
for i, v in enumerate(ver):
    if vmax == v:
        vs.append(i)

ans = hmax + vmax
for k1 in hs:
    for k2 in vs:
        if f[k1][k2] == 0:
            print(ans)
            exit()
print(ans - 1)

Submission status: Time Limit Exceeded

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

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

hor = defaultdict(int)
ver = defaultdict(int)
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hs = []
hmax = max(hor.values())
for k, v in hor.items():
    if hmax == v:
        hs.append(k)
vs = []
vmax = max(ver.values())
for k, v in ver.items():
    if vmax == v:
        vs.append(k)

ans = hmax + vmax
i = 0
for k1 in hs:
    for k2 in vs:
        if f[k1][k2] == 0:
            print(ans)
            exit()
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
def solve(H, M, W, bombs):
    count_h = [0 for _ in range(H)]
    count_w = [0 for _ in range(W)]
    for b in bombs:
        count_h[b[0]] += 1
        count_w[b[1]] += 1
    max_h = max(count_h)
    max_w = max(count_w)
    points_h = [i for i, c in enumerate(count_h) if c == max_h]
    points_w = [i for i, c in enumerate(count_w) if c == max_w]
    ans = max_h + max_w
    if _find_cross_bomb(points_h, points_w, bombs):
        ans -= 1
    print(ans)


def _find_cross_bomb(points_h, points_w, bombs):
    c = 0
    for b in bombs:
        if (b[0]) in points_h:
            if (b[1]) in points_w:
                c += 1
    return c == len(points_h) * len(points_w)


if __name__ == "__main__":
    H, W, M = map(int, input().split())
    bombs = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
    solve(H, M, W, bombs)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

hor = defaultdict(int)
ver = defaultdict(int)
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hor = sorted(hor.items(), key=lambda x:-x[1])
ver = sorted(ver.items(), key=lambda x:-x[1])

ans = hor[0][1] + ver[0][1]
i = 0
while i < len(hor) and hor[i][1] == hor[0][1]:
    j = 0
    while j < len(ver) and ver[j][1] == ver[0][1]:
        if f[hor[i][0]][ver[j][0]] == 0:
            print(ans)
            exit()
        j += 1
    i += 1
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solve():
    H, W, M = map(int, input().split())
    dh, dw = Counter(), Counter()
    used = set()

    for _ in range(M):
        h, w = map(int, input().split())
        dh[h] += 1
        dw[w] += 1
        used.add((h, w))

    ih = dh.most_common()
    iw = dw.most_common()

    h, counth = ih[0]
    w, countw = iw[0]
    ans = counth + countw - ((h, w) in used)

    for h, counth in ih:
        for w, countw in iw:
            b = counth + countw - ((h, w) in used)
            if b<ans:
                break
            ans = b
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

H, W, M = map(int, input().split())
dh, dw = defaultdict(int), defaultdict(int)
used = set()

for _ in range(M):
    h, w = map(int, input().split())
    dh[h] += 1
    dw[w] += 1
    used.add((h, w))

ih = sorted(dh.items(), key=lambda x:-x[1])
iw = sorted(dw.items(), key=lambda x:-x[1])

h, counth = ih[0]
w, countw = iw[0]
ans = counth + countw - ((h, w) in used)

for h, counth in ih:
    for w, countw in iw:
        b = counth + countw - ((h, w) in used)
        if b<ans:
            break
        ans = b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

H, W, M = map(int, input().split())
dh, dw = defaultdict(int), defaultdict(int)
used = set()

for _ in range(M):
    h, w = map(int, input().split())
    dh[h] += 1
    dw[w] += 1
    used.add((h, w))

ih = sorted(dh.items(), key=lambda x:-x[1])
iw = sorted(dw.items(), key=lambda x:-x[1])

h, counth = ih[0]
w, countw = iw[0]
ans = counth + countw - ((h, w) in used)

for h, counth in ih:
    for w, countw in iw:
        b = counth + countw - ((h, w) in used)
        if abs(b-ans)>1:
            break
        ans = max(ans, b)
print(ans)