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())
bomb=sorted([list(map(int, input().split())) for _ in range(m)])
res1=[0 for _ in range(h)]
res2=[0 for _ in range(w)]
for i in range(m):
    res1[bomb[i][0]-1]+=1
    res2[bomb[i][1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=[]
for j in range(h):
    if res1[j]>s1:
            l1=[j+1]
            s1=res1[j]
    elif res1[j]==s1:
            l1.append(j+1)
s2=0
l2=[]
for k in range(w):
    if res2[k]>s2:
            l2=[k+1]
            s2=res2[k]
    elif res2[k]==s2:
            l2.append(k+1)
count=0
for l in range(m):
    if bomb[l][0] in l1 and bomb[l][1] in l2:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
cnt_h = [0] * h
cnt_w = [0] * w
bomb = [[False] * w for _ in range(h)]
for _ in range(m):
    y, x = map(int, input().split())
    cnt_h[y - 1] += 1
    cnt_w[x - 1] += 1
    bomb[y - 1][x - 1] = True
    
kouho_h = []
for i in range(h):
    if cnt_h[i] == max(cnt_h):
        kouho_h.append(i)
kouho_w = []
for i in range(w):
    if cnt_w[i] == max(cnt_w):
        kouho_w.append(i)

flag = False
for i in kouho_h:
    for j in kouho_w:
        if bomb[i][j] == False:
            flag = True
if flag:
    print(max(cnt_h) + max(cnt_w))
else:
    print(max(cnt_h) + max(cnt_w) - 1)

Submission status: Time Limit Exceeded

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

h_max = max(h_list)
h_idx = [i for i, j in enumerate(h_list) if j == h_max]
w_max = max(w_list)
w_idx = [i for i, j in enumerate(w_list) if j == w_max]

ans = 0
flg = False
for i in h_idx:
    if flg:
        break
    for j in w_idx:
        tmp = h_list[i] + w_list[j]
        if [i,j] in bom_list:
            tmp -= 1
        else:
            flg = True
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

W,H,M = map(int,input().split())
data2 = [list(map(int,input().split())) for _ in range(M)]
data = np.array(data2)
#print(data)
ans = 0
for x in range(1,H+1):
    for y in range(1,W+1):
        #print(np.array([y,x]))
        count = np.count_nonzero(data == y, axis=0)[0]
        count += np.count_nonzero(data == x, axis=0)[1]
        if ([y,x] in data2):
            count -=1
        if(ans<count):
            ans = count
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int,input().rstrip().split())
l = [[0 for i in range(H)] for j in range(W)]
r = [0]*H
c = [0]*W
for i in range(M):
    h, w = map(int,input().rstrip().split())
    l[w-1][h-1] = 1
    r[h-1] += 1
    c[w-1] += 1
max_r = max(r)
max_c = max(c)
r_i =[i for i, x in enumerate(r) if x == max_r]
c_j =[i for i, x in enumerate(c) if x == max_c]
ans = max_r+max_c-1
for i in r_i:
    for j in c_j:
        if l[j][i] == 0:
            ans = max_r+max_c
            break
    else:
        continue
    break
print(ans)

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

    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]
        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]
        d.append((x-1,y-1))

    if r_max==0:
        print(c_max)
    elif c_max==0:
        print(r_max)
    else:
        u=[]
        for i in c.keys():
            if c[i]==c_max:
                u.append(i)
        s=r_max+c_max-1
        for j in r.keys():
            if r[j]==r_max:
                for k in u:
                    if (j,k) not in d:
                        s+=1
                        print(s)
                        return
        print(s)

go()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = (int(i) for i in input().split())

hw = set()
hh = [0] * H
ww = [0] * W

for i in range(M):
    ht , wt = (int(i) for i in input().split())
    hw.add((ht-1) * W + wt - 1)
    hh[ht-1] += 1
    ww[wt-1] += 1

hhh = max(hh)
ih = [i for i, x in enumerate(hh) if x == hhh]

www = max(ww)
iw = [i for i, x in enumerate(ww) if x == www]

minus = 1
for iih in ih:
    for iiw in iw:
        if iih * W + iiw not in hw:
            minus = 0


print(hhh + www - minus)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
pos = [list(map(int,input().split())) for i in range(m)]
ans = 0
for i in range(h):
  for j in range(w):
    cnt = 0
    for k in range(h):
      if [k+1,j+1] in pos:
        cnt += 1
    for l in range(w):
      if [i+1,l+1] in pos:
        cnt += 1
    if [i+1,j+1] in pos:
        cnt -= 1
    ans = max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hs = {}
ws = {}
L = []

for i in range(m):
    a = list(map(int,input().split()))
    L.append(a)
    if a[0] in hs:
        hs[a[0]] += 1
    else:
        hs[a[0]] = 1
    if a[1] in ws:
        ws[a[1]] += 1
    else:
        ws[a[1]] = 1
    
#print(hs,ws)
max_kvh = [kv for kv in hs.items() if kv[1] == max(hs.values())]
max_kvw = [kv for kv in ws.items() if kv[1] == max(ws.values())]
#print(max_kvh,max_kvw)

ans = 0
for i in max_kvh:
    for j in max_kvw:
        if [i[0],j[0]] in L:
            ans = i[1]+j[1]-1
        else:
            ans = i[1]+j[1]
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input().split()))
hl=[]
wl=[]
hc=[0]*h
wc=[0]*w
mp=[]
for j in range(m):
    h1,w1=[int(j) for j in input().split()]
    hl.append(h1)
    wl.append(w1)
for i in range(m):
    x=hl[i]-1
    y=wl[i]-1
    z=y*h+x
    hc[x]+=1
    wc[y]+=1
    mp.append(z)
mx=max(hc)
my=max(wc)
lmx=[]
lmy=[]
for p in range (h):
    if hc[p]==mx:
        lmx.append(p)
for q in range (w):
    if wc[q]==my:
        lmy.append(q)
zzx=len(lmx)
zzy=len(lmy)
zzz=1
if zzx*zzy<=m:
    for s in range(zzx):
        ss=lmx[s]
        for t in range(zzy):
            tt=lmy[t]
            uu=tt*h+ss
            if uu not in mp:
                zzz=0
else:
    zzz=0
print(mx+my-zzz)

Submission status: Time Limit Exceeded

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

h_list = []
w_list = []
hw_list = []

for m in range(M):
    h_buf, w_buf = map(int, input().split())
    h_list.append(h_buf)
    w_list.append(w_buf)
    hw_list.append([h_buf, w_buf])

h_c = collections.Counter(h_list)
w_c = collections.Counter(w_list)

M = 0
count_h = 0
count_w = 0
M_j = 0

for l in h_c.most_common():
    if count_h > l[1]: break
    count_h = l[1]
    i = l[0]
    M_i = count_h
    for s in w_c.most_common():
        if count_w > s[1]: break
        count_w = s[1]
        j = s[0]
        M_buf = count_w
        if [i,j] in hw_list:
            M_buf -= 1
        if M_buf>M_j:
            M_j = M_buf

print(M_i + M_j)

Submission status: Time Limit Exceeded

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

hdic = {}
wdic = {}
hws = []

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
    else:
        hdic[h] = 1
    
    if w in wdic.keys():
        wdic[w] += 1
    else:
        wdic[w] = 1
    hws.append([h, w])

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

for k, v in hdic.items():
    if v == hmax:
        hs.append(k)

for k, v in wdic.items():
    if v == wmax:
        ws.append(k)

f = 1
for h in hs:
    for w in ws:
        if [h, w] not in hws:
            f = 0
            break
    if f == 0:
        break

print(hmax + wmax - f)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb_h = [0]*h
bomb_w = [0]*w
place = [[0 for _ in range(w)] for _ in range(h)]
for _ in range(m):
  x,y=map(int,input().split())
  bomb_h[x-1]+=1
  bomb_w[y-1]+=1
  place[x-1][y-1] = 1
x_cand = list()
x_max = 0
for x in range(h):
  if x_max < bomb_h[x]:
    x_cand = [x]
    x_max = bomb_h[x]
  elif x_max == bomb_h[x]:
    x_cand.append(x)
y_cand = list()
y_max = 0
for y in range(w):
  if y_max < bomb_w[y]:
    y_cand = [y]
    y_max = bomb_w[y]
  elif y_max == bomb_w[y]:
    y_cand.append(y)
ans = 0
for x in x_cand:
  for y in y_cand:
    ans = max(ans, x_max+y_max-place[x][y])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, M = [int(x) for x in input().split()]
    HW = [[int(x) for x in input().split()] for _ in range(M)]

    x = set()

    hc = collections.Counter()
    wc = collections.Counter()

    for h, w in HW:
        hc[h] += 1
        wc[w] += 1
        x.add((h, w))

    ans = 0
    hcma = hc.most_common()[0][1]
    wcma = wc.most_common()[0][1]
    for a in hc.most_common():
        if a[1] != hcma:
            break
        for b in wc.most_common():
            if b[1] != wcma:
                break
            if (a[0], b[0]) in x:
                ans = max(ans, hcma + wcma - 1)
            else:
                ans = max(ans, hcma + wcma)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
##
for _ in range(1):
    r,c,m=cin()
    d=dd(list)
    ro=[0]*r
    co=[0]*c
    for i in range(m):
        x,y=cin()
        ro[x-1]+=1
        co[y-1]+=1
        d[x-1]+=[y-1]

    k1=sorted(list(set(ro)))
    k2=sorted(list(set(co)))
    ans=0
    mar1=k1[-1];mac1=k2[-1];
    mar2=mar1;mac2=mac1;mar=[];mac=[]
    if(len(k1)>1):
        mar2=k1[-2]
    if(len(k2)>1):
        mac2=k2[-2]
    for i in range(r):
        if(ro[i]==mar1 or ro[i]==mar2):
            mar+=[i]
    for i in range(c):
        if(co[i]==mac1 or co[i]==mac2):
            mac+=[i]
##    print(mar ,mac)
    for i in mar:
        for j in mac:
            t=0
            if(j in d[i]):t=-1
            ans=max(ans,ro[i]+co[j]+t)
    print(ans)
    
    
    
    
    

                    
                
    

    

        


    
        

    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bom=[[0 for i in range(w)] for j in range(h)]
hl=[0]*h
wl=[0]*w

for i in range(m):
    ha,wa=map(int,input().split())
    bom[ha-1][wa-1]=1
    hl[ha-1]+=1
    wl[wa-1]+=1

hm=max(hl)
wm=max(wl)
hi=[i for i, v in enumerate(hl) if v == hm]
wi=[i for i, v in enumerate(wl) if v == wm]

ans=hm+wm-1

for i in hi:
    for j in wi:
        if bom[i][j]==0:
            ans+=1
            break
    else:
        continue
    break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[set() for _ in range(h)]
for i in range(m):
  h1,w1=map(int,input().split())
  l[h1-1].add(w1-1)
  lh[h1-1]+=1
  lw[w1-1]+=1
hmax=max(lh)

ans=0
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lw2=lw[:]
    for m in l[i]:
      lw2[m]-=1
    ans=max(ans,hmax+max(lw2))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
tgts=set()
for _ in range(M):
    i,j=map(int,input().split())
    tgts.add((i,j))

rows=[0]*(H+1)
cols=[0]*(W+1)

for i,j in tgts:
    rows[i]+=1
    cols[j]+=1

ii=max(rows)
jj=max(cols)

ia=[]
try:
    i=1
    while True:
        i=rows.index(ii,i)
        ia.append(i)
        i+=1
except:
    pass
    
ja=[]
try:
    j=1
    while True:
        j=cols.index(jj,j)
        ja.append(j)
        j+=1
except:
    pass



ans=0
for i in ia:
    for j in ja:
        k=rows[i]+cols[j]
        if (i,j) in tgts:
            k-=1
        ans=max(ans,k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hw = [["." for j in range(w)] for i in range(h)]
l = [list(map(int, input().split())) for i in range(m)]
ht = [0] * h
wt = [0] * w
for i in range(m):
    hw[l[i][0]-1][l[i][1]-1] = "#"
    ht[l[i][0]-1] += 1
    wt[l[i][1]-1] += 1
ans = 0
for i in range(h):
    ans = max(ans, max([wt[j]-1 if hw[i][j] == "#" else wt[j] for j in range(w)])+ht[i])
print(ans)

Submission status: Time Limit Exceeded

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

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

hw = []

for _ in range(H):
    hw.append([0] * W)

for _ in range(M):
    a,b = list(map(int,input().split()))
    h[a - 1] += 1
    w[b - 1] += 1
    hw[a - 1][b - 1] += 1
    
hm = max(h)
wm = max(w)

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

for x in hp:
    for y in wp:
        if hw[x][y] == 0:
            print(hm + wm)
            exit()
else:
    print(hm + wm - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=[]
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.append([x,y])
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
u=0
c=0
for i in a:
    for j in b:
        if [i,j] in plot:
            u+=1
        c+=1
ans=x+y
if u==c:
    print(ans-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

Hc = [0 for i in range(H)]
Wc = [0 for i in range(W)]
HW = [[0 for i in range(W)] for i in range(H)]

for m in range(M):
  h, w = map(int, input().split())
  Hc[h - 1] += 1
  Wc[w - 1] += 1
  HW[h - 1][w - 1] = 1
Hcmax = max(Hc)
Hcmax_idx = [i for i, x in enumerate(Hc) if x == Hcmax] 
Wcmax = max(Wc)
Wcmax_idx = [i for i, x in enumerate(Wc) if x == Wcmax] 

ans = 0
for i in Hcmax_idx:
  for j in Wcmax_idx:
    if HW[i][j] == 1:
      t = Hcmax + Wcmax - 1
    else:
      t = Hcmax + Wcmax
    ans = max(ans, t)
print(ans)

Submission status: Time Limit Exceeded

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

column = [0] * H
row = [0] * W

for item in P:
  column[item[0] -1] += 1
  row[item[1] -1] += 1
  
column_max = [i for i, x in enumerate(column) if x == sorted(column, reverse=True)[0]]
row_max = [i for i, x in enumerate(row) if x == sorted(row, reverse=True)[0]]

flag = 0
for i in column_max:
  for j in row_max:
    if [i+1, j+1] not in P:
      flag = 1
      break
if flag == 1:
  print(max(column) + max(row))
elif flag == 0:
  print(max(column) + max(row) -1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
r=dict()
c=dict()
pos=[]
for i in range(m):
    row,col=map(int,input().split())
    if(row in r):
        r[row]+=1
    else:
        r[row]=1
    if(col in c):
        c[col]+=1
    else:
        c[col]=1

    pos.append(str(row)+str(col))

ans=-100
for i in r.keys():
    for j in c.keys():
        tmp=r[i]+c[j]
        if((str(i)+str(j)) in pos):
            tmp-=1
        ans=max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
a,b,m = map(int,input().split())
data = []
H,W = set(),set()
for i in range(m):
  h,w = map(int,input().split())
  data.append([h,w])
  H.add(h)
  W.add(w)
H = sorted(list(H))
W = sorted(list(W))
comp = [[bisect_right(H,h)-1,bisect_right(W,w)-1] for h,w in data]
data = [[0 for i in range(len(W))] for j in range(len(H))]
for p,q in comp:
  data[p][q] = 1
y = [sum(data[j])for j in range(len(H))]
t = [sum([data[i][j] for i in range(len(H))]) for j in range(len(W))]

res = 0
for i,p in enumerate(y):
  for j,q in enumerate(t):
    res = max(res,p+q-data[i][j])

print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int,input().split())
import collections
flag = 0

hw = [list(map(int,input().split())) for x in range(M)]
h = [0]*H #その行に何個対象があるか
w = [0]*W

for p in range(M):
    h[hw[p][0]-1] += 1
    w[hw[p][1]-1] += 1


hmaxichi = [i for i, x in enumerate(h) if x == max(h)]
wmaxichi = [i for i, x in enumerate(w) if x == max(w)]


for q in range(len(hmaxichi)):
    for r in range(len(wmaxichi)):
        if [hmaxichi[q]+1,wmaxichi[r]+1] not in hw:
            flag = 1 #1なら爆破したい場所に爆弾がない場所がある
            break
    else:
        continue
    break


if flag == 1:
    print(max(h)+max(w))
else:
    print(max(h)+max(w)-1)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
h,w,m=map(int,input().split())
a=[0 for i in range(h+1)]
b=[0 for i in range(w+1)]

v={}
for i in range(m):
    x,y=map(int,input().split())
    # v.append([x,y])
    v[(x,y)]=1
    a[x]+=1
    b[y]+=1
    

maxx=max(a)
aa=[]
for i in range(1,len(a)):
    if a[i]==maxx:
        aa.append(i)

maxy=max(b)
bb=[]
for i in range(1,len(b)):
    if b[i]==maxy:
        bb.append(i)

ans=0
for i in range(len(aa)):
    for j in range(len(bb)):
        if (aa[i],bb[j]) in v:
            ans=max(ans,a[aa[i]]+b[bb[j]]-1)
            
        else:
            ans=max(ans,a[aa[i]]+b[bb[j]])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W, M = map(int, input().split())

h_list = [0 for _ in range(H + 1)]
w_list = [0 for _ in range(W + 1)]
m_list = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(M):
    h, w = map(int, input().split())
    h_list[h] += 1
    w_list[w] += 1
    m_list[h][w] = 1

max_h_list = []
max_h = -1
for i in range(H + 1):
    if max_h == h_list[i]:
        max_h_list.append(i)
    elif max_h < h_list[i]:
        max_h = h_list[i]
        max_h_list = [i]

max_w_list = []
max_w = -1
for i in range(W + 1):
    if max_w == w_list[i]:
        max_w_list.append(i)
    elif max_w < w_list[i]:
        max_w = w_list[i]
        max_w_list = [i]

adjust_dupl = 1
for i in range(len(max_h_list)):
    for j in range(len(max_w_list)):
        if m_list[max_h_list[i]][max_w_list[j]] == 0:
            adjust_dupl = 0
            break
    if adjust_dupl == 0:
        break
print(max_h + max_w - adjust_dupl)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
from collections import defaultdict
dw = defaultdict(list)
dh = defaultdict(list)
for m in range(M):
  h,w=map(int,input().split())
  dh[h].append(w)
  dw[w].append(h)
Lh=0
kh=[]
for h in dh.keys():
  if len(dh[h])>Lh:
    Lh=len(dh[h])
    kh=[h]
  if len(dh[h])==Lh:
    kh.append(h)
Lw=0
a=0
for KH in kh:
  for w in dw.keys():
    if KH in dw[w]:
      a=1
    else:
      a=0
    if len(dw[w])-a>Lw:
      Lw=len(dw[w])-a
print(Lh+Lw)

Submission status: Time Limit Exceeded

Solution code:
import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = [i for i in range(300001) if x[i] == mx]
y1 = [i for i in range(300001) if y[i] == my]
z1 = list(itertools.product(x1, y1))
if all(i in z for i in z1): print(mx + my - 1)
else: print(mx + my)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

    retu = Counter()
    gyo = Counter()

    ipt = [[] for _ in range(H)]

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].append(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())

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 = [ str(i) + '_' + str(j) for i in xlist for j in ylist ]
tlist = [ str(i[0]) + '_' + str(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:
import random
h,w,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
exist = []
tate = [[0,i] for i in range(h)]
yoko = [[0,i] for i in range(w)]

for y,x in lis:
    exist.append(format(y).zfill(6)+format(x).zfill(6))
    tate[y-1][0] += 1
    yoko[x-1][0] += 1

tate.sort(key=lambda x:x[0],reverse=True)
yoko.sort(key=lambda x:x[0],reverse=True)

ans = 1
if m >= 2:ans = 2
if h == 1 or w == 1:
    print(m)
    exit()

  # print(tate)
  # print(yoko)

for turn in range(10000):
    i,j = random.randint(0,h-1),random.randint(0,w-1)
    ans = max(ans,tate[i][0]+yoko[j][0]-bool(format(tate[i][1]+1).zfill(6)+format(yoko[j][1]+1).zfill(6) in exist))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
l = [[0 for x in range(w)] for y in range(h)]
lx = [0 for x in range(w)]
ly = [0 for y in range(h)]
for i in range(m):
    y,x = map(int,input().split())
    lx[x-1] += 1
    ly[y-1] += 1
    l[y-1][x-1] = 1
t_x = max(lx)
t_y = max(ly)
flg = 0
for j in range(w):
    if lx[j] == t_x:
        for k in range(h):
            if ly[k] == t_y:
                if l[k][j] == 0:
                    flg = 1
if flg == 1:
    print(t_x+t_y)
else:
    print(t_x+t_y-1)

Submission status: Time Limit Exceeded

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

# Input#
# n = int(input())
h, w, m = map(int, input().split())
tar_list = []

h_count = [0] * (h + 1)
w_count = [0] * (w + 1)

h_max = 0
w_max = 0

ans = 0
ans_tmp = 0

for i in range(m):
    h_in, w_in = map(int, input().split())
    tar_list.append((h_in, w_in))

    h_count[h_in] += 1
    if h_count[h_in] > h_max:
        h_max = h_count[h_in]

    w_count[w_in] += 1
    if w_count[w_in] > w_max:
        w_max = w_count[w_in]


for i in range(h + 1):
    if h_count[i] == h_max:
        for j in range(w + 1):
            if w_count[j] == w_max:
                if (i, j) in tar_list:
                    ans_tmp = h_count[i] + w_count[j] - 1
                    ans = max(ans, ans_tmp)
                else:
                    ans_tmp = h_count[i] + w_count[j]
                    ans = max(ans, ans_tmp)


print("{}".format(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 = {}
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())

for ki, vi in H.items():
    if vi == HMAX:
        HMAXES.append(ki)
for ki, vi in W.items():
    if vi == WMAX:
        WMAXES.append(ki)

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:
from collections import defaultdict
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]
tate, yoko = defaultdict(int), defaultdict(int)
for h, w in hw:
    tate[h] += 1
    yoko[w] += 1
tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_max, yoko_max = tate[0][1], yoko[0][1]
max_tates, max_yokos = [], []
for t in tate:
    if t[1] == tate_max:
        max_tates.append(t)
    else:
        break
for y in yoko:
    if y[1] == yoko_max:
        max_yokos.append(y)
    else:
        break

for ta in max_tates:
    for yo in max_yokos:
        if (ta[0], yo[0]) not in hw:
            print(tate_max + yoko_max)
            exit()
print(tate_max + yoko_max - 1)

Submission status: Time Limit Exceeded

Solution code:
import random
h,w,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
exist = []
tate = [[0,i] for i in range(h)]
yoko = [[0,i] for i in range(w)]

for y,x in lis:
    exist.append(format(y).zfill(6)+format(x).zfill(6))
    tate[y-1][0] += 1
    yoko[x-1][0] += 1

tate.sort(key=lambda x:x[0],reverse=True)
yoko.sort(key=lambda x:x[0],reverse=True)

ans = 1
if m >= 2:ans = 2
if h == 1 or w == 1:
    print(m)
    exit()

  # print(tate)
  # print(yoko)

for turn in range(1000000):
    i,j = random.randint(0,h-1),random.randint(0,w-1)
    ans = max(ans,tate[i][0]+yoko[j][0]-bool(format(tate[i][1]+1).zfill(6)+format(yoko[j][1]+1).zfill(6) in exist))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]
s=[[0 for i in range(w)] for j in range(h)]
for i in range(m):
    x,y=map(int,input().split())
    s[x-1][y-1]=1
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
for i in range(h):
    if g[i]==max(g):
        G.append(i+1)
for i in range(w):
    if r[i]==max(r):
        R.append(i+1)
f=1
for i in range(len(G)):
    for j in range(len(R)):
        if s[G[i]-1][R[j]-1]==0:
            f=0
            break
print(max(g)+max(r) if f==0 else max(g)+max(r)-1)

Submission status: Time Limit Exceeded

Solution code:
#e
h,w,m=map(int,input().split())
hw=[]
hh=set()
ww=set()
hhh=[0]*h
www=[0]*w
for i in range(m):
    hi,wi=map(int,input().split())
    hi-=1
    wi-=1
    hh.add(hi)
    ww.add(wi)
    hhh[hi]+=1
    www[wi]+=1
    hw.append([hi,wi])
if len(hh)==1 or len(ww)==1:
    print(m)
else:
    ans=0
    maxh=max(hhh)
    for i in hh:
        if hhh[i]==maxh:
            wwww=www.copy()
            for j in range(m):
                if hw[j][0]==i:
                    wwww[hw[j][1]]-=1
            ansi=maxh+max(wwww)
            ans=max(ans,ansi)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
h,w,m=map(int,input().split())
a=[0 for i in range(h+1)]
b=[0 for i in range(w+1)]

v=[]
for i in range(m):
    x,y=map(int,input().split())
    v.append([x,y])
    a[x]+=1
    b[y]+=1
    

maxx=max(a)
aa=[]
for i in range(1,len(a)):
    if a[i]==maxx:
        aa.append(i)

maxy=max(b)
bb=[]
for i in range(1,len(b)):
    if b[i]==maxy:
        bb.append(i)

ans=0
for i in range(len(aa)):
    for j in range(len(bb)):
        if [aa[i],bb[j]] in v:
            ans=max(ans,a[aa[i]]+b[bb[j]]-1)
            
        else:
            ans=max(ans,a[aa[i]]+b[bb[j]])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
b = []
x = [0 for _ in range(w)]
y = [0 for _ in range(h)]
for i in range(m):
  bh,bw = map(int,input().split())
  bh -= 1
  bw -= 1
  b.append((bh,bw))
  x[bw] += 1
  y[bh] += 1
#print(b,x,y)

mxx = max(x)
mxy = max(y)
xb = []
for i in range(w):
  xb.append((x[i],i))
xb.sort(reverse = True)
yb = []
for i in range(h):
  yb.append((y[i],i))
yb.sort(reverse = True)
#print(xb,yb)

for xbi,i in xb:
  if xbi < mxx:
    break
  for ybi,j in yb:
    if ybi < mxy:
      continue
    else:
      if (j,i) not in b:
        print(xbi+ybi)
        exit()
print(mxx+mxy-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
dp = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    dp[hh - 1][ww - 1] += 1


hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0
for i in hhhh:
    for j in wwww:
        if dp[i][j] == 0:
            check = 1
            break
print(hhh + www - (1-check))