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 random

def putmx(lis):
  ret=[]
  mx=max(lis)
  for i in range(len(lis)):
    if mx==lis[i]:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
#inp=[(random.randrange(1,h+1),random.randrange(1,w+1)) for i in range(m)]
hb=[0]*h
wb=[0]*w
bmb=[-1]*h
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  if bmb[hh]==-1:
    bmb[hh]=[ww]
  else:
    bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1

hmx=putmx(hb)
wmx=putmx(wb)
mhb=max(hb)
mwb=max(wb)
#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  for j in wmx:
    if not j in bmb[i]:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
mwi=deque([])
s = [list(map(int, input().split())) for i in range(m)]
lis = [deque([]) for i in range(h)]

for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  lis[a].append(b)
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)

for i in mwi:
  for j in mhi:
    if not i in lis[j]:
      print(mh+mw)
      quit()
      
print(mh+mw-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int, input().split())
#nrow=[0]*H
#ncol=[0]*W
xcoord=[]
ycoord=[]

import collections

for _ in range(M):
	h,w=map(int, input().split())
#	nrow[h-1]+=1
#	ncol[w-1]+=1
	xcoord+=[w-1]
	ycoord+=[h-1]

ncol=collections.Counter(xcoord)
nrow=collections.Counter(ycoord)


#print(nrow) #dict of y-coord
#print(ncol) #dict of x-coord

row_cand=[]
col_cand=[]

a=max(nrow.values())
for i in nrow.keys():
	if nrow[i]==a:
		row_cand+=[i]


#print(row_cand)

b=max(ncol.values())
for i in ncol.keys():
	if ncol[i]==b:
		col_cand+=[i]

#print(col_cand)



#print(xcoord,ycoord)


count_intersection=0
for i in range(len(xcoord)):
	if (xcoord[i] in col_cand) and (ycoord[i] in row_cand):
		count_intersection+=1

if count_intersection==len(col_cand)*len(row_cand):
	print(a+b-1)
else:
	print(a+b)



# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Time Limit Exceeded

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

h,w,m=map(int,input().split())
l=[[0 for i in range(w+1)] for j in range(h+1)]
row=[0 for i in range(h+1)]
col=[0 for j in range(w+1)]

for i in range(m):
    x,y=map(int,input().split())
    l[x][y]=1
    row[x]+=1
    col[y]+=1
    


maxa=0    
for i in range(1,h+1):
    for j in range(1,w+1):
        if(l[i][j]):maxa=max(maxa,row[i]+col[j]-1)
        else:maxa=max(maxa,row[i]+col[j])
        
print(maxa)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = list(map(int,input().split()))
t = [list(map(int,input().split())) for _ in range(m)]
from collections import Counter

x,y = zip(*t)
xcnt = Counter(x)
ycnt = Counter(y)

xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
xylist = [ i*(10**6)+j for i in xlist for j in ylist ]
tlist = [ i[0]*(10**6) + i[1] for i in t ]
if len( set(xylist) - set(tlist) ) == 0:
  print( xcmax + ycmax -1 )
else:
  print( xcmax + ycmax )

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = [[0 for j in range(W+1)] for i in range(H+1)]
for k in range(M):
  a,b = map(int,input().split())
  P[a] += 1
  Q[b] += 1
  A[a][b] = 1
Pmax = max(P)
Qmax = max(Q)
ans = Pmax+Qmax-1
#print(P,Q,A,Pmax,Qmax,ans)
Pindex = [i for i, v in enumerate(P) if v == Pmax]
Qindex = [i for i, v in enumerate(Q) if v == Qmax]
key = 0
for x in Pindex:
  for y in Qindex:
    if A[x][y] == 0:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    h, w, m = map(int, input().split())
    rows = defaultdict(int)
    cols = defaultdict(int)
    d1 = lambda :defaultdict(int)
    d2 = defaultdict(d1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        d2[a-1][b-1] = 1
    rm = max(rows.values())
    cm = max(cols.values())
    rs = [i for i, v in rows.items() if v == rm]
    cs = [i for i, v in cols.items() if v == cm]
    r = rm + cm
    p = set()
    for rse in rs:
        for cse in cs:
            p.add(d2[rse][cse])
    r -= min(p)
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

#maxCount = 0
#for h, count in hList.items():
#  if maxCount<count:
#    maxCount = count
maxCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxCount]


#maxCount = 0
#for w, count in wList.items():
#  if maxCount<count:
#    maxCount = count
maxCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxCount]

counterList = []
for maxH in maxHList:
  for maxW in maxWList:
    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
    #counter = 0
    #for h, w in pList:
    #  #print(h, maxH, w, maxW)
    #  if h==maxH or w==maxW:
    #    counter += 1
    #counterList.append(counter)
print(max(counterList))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
C = [list(map(int, input().split())) for i in range(M)]

h = {}
w = {}
for i in range(M):
    hi = C[i][0]
    wi = C[i][1]
    h[hi] = h.get(hi, 0) + 1
    w[wi] = w.get(wi, 0) + 1

ans = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        count = 0
        if [i, j] in C:
            count = h.get(i, 0) + w.get(j, 0) - 1
        else:
            count = h.get(i, 0) + w.get(j, 0)
        ans = max(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,m = map(int, input().split())
column = [0 for i in range(h+1)]
row = [0 for i in range(w+1)]
column_max = 0
row_max = 0
line = []

for i in range(m):
  a,b = map(int, input().split())
  column[a] += 1
  row[b] += 1
  if column[a] > column_max:
    column_max = column[a]
  if row[b] > row_max:
    row_max = row[b]
  line.append([a,b])
  
column_max_index = [i for i, x in enumerate(np.array(column)) if x == column_max]
row_max_index = [i for i, x in enumerate(np.array(row)) if x == row_max]
par = []
for i in column_max_index:
  for j in row_max_index:
    par.append([i,j])

count = 0
for i in par:
  if i not in line:
    count += 1
    break
if count != 0:
  print(column_max + row_max)
else:
  print(column_max + row_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

ri = row.index(max(row))
rr = rn[ri]
cm = max(col)
rm = max(row)
ans = -1
for x,y in enumerate(row):
  if y!=rm:  continue
  rr = rn[x]
  for i,j in enumerate(col):
    if j==cm:
      if i in rr:
        ans = max(ans,cm+rm-1)
      else:
        ans = max(ans,cm+rm)
print(ans)

Submission status: Time Limit Exceeded

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

hh = defaultdict(int)
ww = defaultdict(int)
ss = set()
for _ in range(m):
    h, w = map(int, input().split())
    ss.add((h, w))
    hh[h] += 1
    ww[w] += 1

mh = max(hh.values())
mw = max(ww.values())
hh = [k for k, v in hh.items() if v == mh]
ww = [k for k, v in ww.items() if v == mw]

ans = 0
for h in hh:
    for w in ww:
        a = 0
        for sh, sw in ss:
            if h == sh or w == sw:
                a += 1
        ans = max(ans, a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
row=defaultdict(int)
col=defaultdict(int)
H,W,M=map(int,input().split())
matrix=[[1 for i in range(W)] for j in range(H)]
for i in range(M):
    h,w=map(int,input().split())
    row[h]+=1
    col[w]+=1
    matrix[h-1][w-1]=0
#print(row)
#print(col)
#for i in matrix:
#    print(*i)
temp=list(row.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt=0
for i in range(W):
    temp=0
    if matrix[a-1][i]==0:
        temp=(b+col[i+1]-1)
    else:
        temp=(b+col[i+1])
    cnt=max(cnt,temp)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w, n = [int(i) for i in input().split()]
boms = []
for _ in range(n):
    boms.append([(int(i) - 1) for i in input().split()])
baks = []
row_sum_max = 0
for i in range(h):
    row_sum = 0
    for bom in boms:
        if bom[0] == i:
            row_sum += 1
    if row_sum >= row_sum_max:
        row_sum_max = row_sum
        row_max_ind = i

bak_max = 0
for j in range(w):
    bak = 0
    for bom in boms:
        if bom[0] == row_max_ind or bom[1] == j:
            bak += 1
    if bak_max < bak:
        bak_max = bak
print(bak_max)

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 = {}
H = {}
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    if not h in H:
        H[h] = 1
    else:
        H[h] += 1
    
    if not w in W:
        W[w] = 1
    else:
        W[w] += 1

    HW[h][w] = 1

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

answer = HMAX + WMAX

for ki, vi in H.items():
    if vi == HMAX:
        HMAXES.append(ki)
for ki, vi in W.items():
    if vi == WMAX:
        for h in HMAXES:
            if HW[h][ki] == 0:
                print(answer)
                sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int, input().split())
M=max(h, w)
lh=[0]*(M+1)
lw=[0]*(M+1)
point=[[-1,-1]]
for i in range(m):
  a,b=map(int, input().split())
  lh[a]=lh[a]+1
  lw[b]=lw[b]+1
  point.append([a,b])

mh=max(lh)
mw=max(lw)

pansh=[]
pansw=[]

for i in range(M+1):
  if lh[i]==mh:
    pansh.append(i)
  if lw[i]==mw:
    pansw.append(i)

d=0

for i in range(len(pansh)):
  for j in range(len(pansw)):
    if [pansh[i], pansw[j]] not in point:
      d=1


if d==0:
  print(mh+mw-1)
else:
  print(mh+mw)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

h, w, m = map(int, sys.stdin.readline().split())
hl = []
wl = []

for _ in range(m):
    hi, wi = map(int, sys.stdin.readline().split())
    hl.append(hi)
    wl.append(wi)

hc = Counter(hl)
wc = Counter(wl)

maxh = max(hc.values())
maxw = max(wc.values())

seth = []
setw = []

for c,num in hc.most_common():
    if num != maxh:
        break
    seth.append(c)

for c,num in wc.most_common():
    if num != maxw:
        break
    setw.append(c)

ans = 0

def cnt(r, c):
    for j in range(m):
        if hl[j] == r and wl[j] == c:

            return -1
    return 0

for hei in seth:
    for wei in setw:
        ans = max(ans, hc[hei]+wc[wei]+cnt(hei, wei))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(H: int, W: int, M: int, h: "List[int]", w: "List[int]"):
    hDict = defaultdict(int)
    wDict = defaultdict(int)
    points = set()
    for i in range(M):
        hDict[h[i]]+=1
        wDict[w[i]]+=1
        points.add((h[i],w[i]))
    hArr = []
    wArr = []
    for hd in hDict:
        he = hDict[hd]
        hArr.append((-he,he,hd))
    for wd in wDict:
        he = wDict[wd]
        wArr.append((-he,he,wd))
    hArr.sort()
    wArr.sort()
    m = 0
    for h in hArr:
        for w in wArr:
            c = h[1] + w[1]
            if (h[2],w[2]) in points:
                c -= 1
            m = max(m,c)
    print(m)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    h = [int()] * (M)  # type: "List[int]"
    w = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        h[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(H, W, M, h, w)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    h[(AA[i][0]-1)]+=1
    w[(AA[i][1]-1)]+=1
max_h=max(h)
max_w=max(w)
flag=1
for i in range(H):
    if (h[i]==max_h)&(flag==1):
        for j in range(W):
            if w[j]==max_w:
                if [i+1,j+1] in AA:
                    flag=1
                else:
                    flag=0
                    break
print(max_h+max_w-flag)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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

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

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []


for i in range(1, H + 1):
    if h_cnt[i] == h_max:
        h_max_idx.append(i)

for i in range(1, W + 1):
    if w_cnt[i] == w_max:
        w_max_idx.append(i)

# print(h_max_idx)
# print(w_max_idx)

# if len(h_max_idx)>=10**2:
#     h_max_idx = h_max_idx[:10**2]
# if len(w_max_idx)>=10**2:
#     w_max_idx = w_max_idx[:10**2]

ans = 0

for i in h_max_idx:
    for j in w_max_idx:
        tmp = h_cnt[i] + w_cnt[j]
        if hw_dict[(i, j)] == 1:
            tmp -= 1
        ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from sys import stdin
def main():
    h,w,m= map(int, input().split())
    a = [list(map(int, stdin.readline().split())) for _ in range(m)]
    b=[a[i][0] for i in range(m)]
    c=[a[i][1] for i in range(m)]
    v=Counter(b).most_common()[0][1]
    w=Counter(c).most_common()[0][1]
    i=[j[0] for j in list(Counter(b).items()) if j[1]==v]
    i2=[j[0] for j in list(Counter(c).items()) if j[1]==w]
    l=0
    
    for k in i:
        for t in i2:
            
            if([k,t] not in a):
                print(v+w)
                l=1
                break
            
        else:
            continue
        break
    if(l==0):
        print(v+w-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hwmatrix = [[0 for _ in range(W)] for _ in range(H)]

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hwmatrix[h-1][w-1] = 1

    hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    flag = False
    for h in hmax:
        for w in wmax:
            if hwmatrix[h][w] == 0:
                flag = True
                break

    if flag:
        print(Hlist[h] + Wlist[w])
    else:
        print(Hlist[h] + Wlist[w] - 1)





if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

row_dict = defaultdict(int)
col_dict = defaultdict(int)
row_col_dict = defaultdict(list)
for _ in range(m):
    row, col = map(int, input().split())
    row_dict[row] += 1
    col_dict[col] += 1
    row_col_dict[row].append(col)

max_rows = [k for k, v in row_dict.items() if v == max(row_dict.values())]
max_cols = [k for k, v in col_dict.items() if v == max(col_dict.values())]
ans = 0

for row in max_rows:
    for col in max_cols:
        bom = row_dict[row] + col_dict[col]
        if col in row_col_dict[row]:
            bom -= 1
        ans = max(ans, bom)

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(M):
  x,y=map(int,input().split())
  BD[x-1][y-1]=1

maxH,maxW=0,0
C,R=0,0
for i in range(H):
  s=sum(BD[i])
  if s>maxH:
    maxH=s
    R=i
for j in range(W):
  BD[R][j]=0

for j in range(W):
  s=0
  for i in range(H):
    s+=BD[i][j]
  if maxW<s:
    maxW=s
    C=i
print(maxH+maxW)

Submission status: Time Limit Exceeded

Solution code:
def go():
    h, w, m = map(int, input().split(" "))
    r, c = {},{}
    d = []
    r_max,c_max=0,0
    u,v=[],[]
    for i in range(m):
        x, y = map(int, input().split(" "))
        if (x - 1) in r.keys():
            r[x - 1] += 1
        else:
            r[x - 1] = 1
        if r[x - 1] > r_max:
            r_max = r[x - 1]
            u=[x-1]
        elif r[x-1]==r_max:
            u.append(x-1)
        if (y - 1) in c.keys():
            c[y - 1] += 1
        else:
            c[y - 1] = 1
        if c[y - 1] > c_max:
            c_max = c[y - 1]
            v=[y-1]
        elif c[y-1]==c_max:
            v.append((y-1))
        d.append((x-1,y-1))

    if r_max==0:
        print(c_max)
    elif c_max==0:
        print(r_max)
    else:
        s=r_max+c_max-1
        for j in u:
            for k in v:
                if (j,k) not in d:
                    s+=1
                    print(s)
                    return
        print(s)

go()

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

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

b = [[False] * W for _ in range(H)]
r = [0] * H
c = [0] * W
for _ in range(M):
    h, w = map(int, input().split())
    b[h-1][w-1] = True
    r[h-1] += 1
    c[w-1] += 1

list_r, list_c = [], []
max_r, max_c = max(r), max(c)

for i in range(H):
    if r[i] == max_r:
        list_r.append(i)

for i in range(W):
    if c[i] == max_c:
        list_c.append(i)

for v1 in list_r:
    for v2 in list_c:
        if not b[v1][v2]:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
import sys
h,w,m = (int(x) for x in input().split())
hw = []
for _ in range(m):
    hw.append([int(x) for x in input().split()])

np_hw = np.array(hw)

c_h = collections.Counter(np_hw[:,0])
c_w = collections.Counter(np_hw[:,1])

max_h_list = []
max_w_list = []
for i in range(len(c_h)):
    if c_h.most_common()[i][1] == c_h.most_common()[0][1]:
        max_h_list.append(c_h.most_common()[i][0])
    else:
        break
for i in range(len(c_w)):
    if c_w.most_common()[i][1] == c_w.most_common()[0][1]:
        max_w_list.append(c_w.most_common()[i][0])
    else:
        break

ans = c_h.most_common()[0][1]+c_w.most_common()[0][1]-1
for i in max_h_list:
    for j in max_w_list:
        if [i,j] not in hw:
            ans += 1
            print(ans)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from functools import lru_cache
import sys
from itertools import product,combinations
from functools import reduce,lru_cache
import heapq

def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def list_t(l): return vfunc(lambda *args:args)(*l)

def rvfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:rvfunc(f)(*x,**kwargs) if all(vfunc(lambda y:isinstance(y,list))(x)) else f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

s=rvfunc(int)(reader())
h,w,m=s[0]
hl,wl = [0]*h,[0]*w
hw=s[1:]
hh,ww = list_t(hw)
for i in range(len(hw)):
    hl[hh[i]-1]+=1
    wl[ww[i]-1]+=1
hlmax,wlmax = vfunc(max)([hl,wl])
hlidx = tuple(filter(lambda a:hl[a]==hlmax,range(len(hl))))
wlidx = tuple(filter(lambda a:wl[a]==wlmax,range(len(wl))))
minus = 1
for i in hlidx:
    for j in wlidx:
        if not [i+1,j+1] in hw:
            minus=0
            break
print(max(hl)+max(wl)-minus)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

h_dict = dict()
w_dict = dict()

targets = [None] * (3 * 10 ** 5)

for i in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets[i] = (temp_h, temp_w)

max_h = max(h_dict.values())
max_w = max(w_dict.values())

h_candidates = [k for k, v in h_dict.items() if v == max_h]
w_candidates = [k for k, v in w_dict.items() if v == max_w]

for temp_h, temp_w in itertools.product(h_candidates, w_candidates):
    if not ((temp_h, temp_w) in targets):
        print(h_dict[temp_h] + w_dict[temp_w])
        break
else:
    print(h_dict[temp_h] + w_dict[temp_w] - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    h, w, m = map(int, input().split())
    rows = [0] * h
    cols = [0] * w
    d1 = lambda :defaultdict(int)
    d2 = defaultdict(d1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        d2[a-1][b-1] = 1
    rm = max(rows)
    cm = max(cols)
    rs = [i for i, v in enumerate(rows) if v == rm]
    cs = [i for i, v in enumerate(cols) if v == cm]
    r = rm + cm
    p = set()
    for rse in rs:
        for cse in cs:
            p.add(d2[rse][cse])
    r -= min(p)
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#左の最頻と右の最頻合計すればいいんじゃないの？
#でも最頻がお互い3万種類までありえる
#その場合は最頻をminから順番に組み合わせていって、最頻＋最頻が該当した瞬間breakでよい
#これなら処理回数はmax3万？だし
#最頻+最頻-1しかない場合は、左右ぞれぞれ2位×1位を同様に試すいやこれいらんわ
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []

for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)

countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)

leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す

for i in range(leftkeyN):
    if flag != 0:
        break
    else:
        for P in range(rightkeyN):
            for T in range(M):
                if c[T] == [leftkeys[i],rightkeys[P]]:
                    cnt = cnt + 1
            if cnt == 0:
                flag = flag + 1
                break
            else:
                cnt = 0

if flag == 0:
    print(int(tempmax - 1))
else:
    print(int(tempmax))

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
for i in range(m):
    h, m = map(int, input().split())
    lst_.append([h, m])

lst = np.array(lst_)
h_lst = collections.Counter(lst[:,0])
w_lst = collections.Counter(lst[:,1])

def get_cand(sub_lst):
    sub_lst = sub_lst.most_common()
    cand = []
    for sub in sub_lst:
        if sub[1] != sub_lst[0][1]:
            break
        cand.append(sub[0])
    return cand, sub_lst[0][1]

h_cand, h_count = get_cand(h_lst)
w_cand, w_count = get_cand(w_lst)

flag = False
for h in h_cand:
    if flag:
        break
    for w in w_cand:
        if not [h,w] in lst_:
            #print("bomber: ", h_count, w_count)
            flag = True
            break
ans = h_count + w_count
if flag:
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
h, w, m = map(int, input().split())
A = []
B = []
points = set()
for _ in range(m):
    a, b = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    points.add((a - 1,b - 1))
ac = Counter(A).most_common()
bc = Counter(B).most_common()
#print(ac, bc, points)
x = ac[0][1]
y = bc[0][1]
acm = [i for i, j in ac if j == x]
bcm = [i for i, j in bc if j == y]

ans = 0
for i in acm:
    for j in bcm:
        tmp = x + y
        if (i, j) in points:
            tmp -= 1
        ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

bomb = [[0 for j in range(w)] for i in range(h)]
for i in range(m):
    bomb_h, bomb_w = map(int, input().split())
    bomb[bomb_h-1][bomb_w-1] = 1

sum_hor = []
for i in range(h):
    sum_hor.append(sum(bomb[i]))

sum_ver = []
transpose = [x for x in zip(*bomb)]
for i in range(w):
    sum_ver.append(sum(transpose[i]))

cost = []
for i in range(h):
    for j in range(w):
        if bomb[i][j] == 1:
            cost.append(sum_hor[i] + sum_ver[j] - 1)
        else:
            cost.append(sum_hor[i] + sum_ver[j])

print(max(cost))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
H , W , M = map(int,input().split())
h = [0]*M
w = [0]*M
for i in range(M):
  h[i] , w[i] = map(int,input().split())
G1 = deque([0]*H)
G2 = deque([0]*W)
for i in range(M):
  temp = h[i] - 1
  G1[temp] += 1
for  i in range(M):
  temp = w[i] - 1
  G2[temp] += 1
G3 = [[h[i] - 1 , w[i] - 1] for i in range(M)]
M1 = max(G1)
M2 = max(G2)
M1L = []
M2L = []
for i in range(H):
  if G1[i] == M1:
    M1L.append(i)
for j in range(W):
  if G2[j] == M2:
    M2L.append(j)
c = 0
for i in M1L:
  for j in M2L:
    if [i,j] not in G3:
      c = 1
      break
  if c ==1:
    break
if c == 1:
  print(M1 + M2)
else:
  print(M1 + M2 - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
l=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(m):
    x,y=map(int,input().split())
    l[x][y]=1
    
row=[0 for i in range(h+1)]
col=[0 for j in range(w+1)]

for i in range(1,h+1):
    row[i]=sum(l[i])
    
        
for j in range(1,w+1):
    sumi=0
    for i in range(1,h+1):
        sumi+=l[i][j]
    col[j]=sumi
maxa=0    
for i in range(1,h+1):
    for j in range(1,w+1):
        if(l[i][j]):maxa=max(maxa,row[i]+col[j]-1)
        else:maxa=max(maxa,row[i]+col[j])
        
print(maxa)

Submission status: Time Limit Exceeded

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

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

bomb_h = [0] * H
bomb_w = [0] * W
grid = [[False] * W for _ in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    grid[h-1][w-1] = True

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if not grid[h][w]:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
L = [[0 for _ in range(W)] for _ in range(H)]
for i in range(M):
    h,w = map(int,input().split())
    L[h-1][w-1] += 1
y = 0
yy = 0
yl = []
t = 0
tt = 0
tl = []
for i in range(H):
    a = sum(L[i])
    if a > y:
        y = a
        yy = i
        yl = [i]
    elif a == y:
        yl.append(i)
R = list(zip(*L))
for i in range(W):
    b = sum(R[i])
    if b > t:
        t = b
        tt = i
        tl = [i]
    elif b == t:
        tl.append(i)
if len(yl) == 1 and len(tl) != 1:
    for i in range(len(tl)):
        if L[yy][tl[i]] == 0:
            tt = tl[i]
            break
elif len(tl) == 1 and len(yl) != 1:
    for i in range(len(yl)):
        if L[yl[i]][tt] == 0:
            yy = yl[i]
elif len(yl) != 1 and len(tl) != 1:
    s = True
    for i in range(len(yl)):
        if s:
            for j in range(len(tl)):
                if L[yl[i]][tl[j]] == 0:
                    yy = yl[i]
                    tt = tl[j]
                    s = False
                    break
if L[yy][tt] == 1:
    print(y + t - 1)
else:
    print(y + t)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
countH = [[h, 0] for h in range(H)]
countW = [[w, 0] for w in range(W)]
Bh = {}

for i in range(M):
  h, w = map(int, input().split())
  h, w = h-1, w-1
  if h in Bh:
    Bh[h].add(w)
  else:
    Bh[h] = {w}
  countH[h][1] += 1
  countW[w][1] += 1

countH.sort(reverse=True, key=lambda x: x[1])
countW.sort(reverse=True, key=lambda x: x[1])
#print(countH)
#print(countW)
#rint(Bh)

maxh = countH[0][1]
maxw = countW[0][1]
ans = maxh + maxw
ch = [countH[0][0]]
i = 1
while i < H and countH[i][1]==maxh:
  ch.append(countH[i][0])
  i += 1
cw = [countW[0][0]]
i = 1
while i < W and countW[i][1]==maxw:
  cw.append(countW[i][0])
  i += 1
flag = False
for h in ch:
  for w in cw:
    #print(h,w)
    if h not in Bh or w not in Bh[h]:
      flag = True
if flag:
  print(ans)
else:
  print(ans-1)

Submission status: Time Limit Exceeded

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

ans=0

for i in range(h):

    for j in range(w):

        count=0

        for k in range(m):

            if i+1 == int(mat[k][0]) or j+1 == int(mat[k][1]):

                count+=1

            k+=1
        
        if count>ans:

            ans=count
            
        j+=1

    i+=1

print(ans)