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
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W, M = MI()
    Hlist = [[0, i] for i in range(H)]
    Wlist = [[0, i] for i in range(W)]
    Dlist = [[] for i in range(H)]
    H_max = -float('inf')
    W_max = -float('inf')
    
    for i in range(M):
        h, w = MI()
        Hlist[h-1][0]+=1
        Wlist[w-1][0]+=1
        Dlist[h-1].append(w-1)
        H_max = max(H_max, Hlist[h-1][0])
        W_max = max(W_max, Wlist[w-1][0])
    Hlist = [temp[1] for temp in Hlist if temp[0] == H_max]
    Wlist = [temp[1] for temp in Wlist if temp[0] == W_max]
    ans = H_max+W_max-1

    for index1 in Hlist:
        for index2 in Wlist:
            if not index2 in Dlist[index1]:
                ans += 1
                break
        else:
            continue
        break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, m=map(int,input().split())
H=[0]*h
W=[0]*w
HW=[]

for i in range(m) :
    h_, w_=map(int,input().split())
    H[h_-1]+=1
    W[w_-1]+=1
    HW.append([h_-1,w_-1])
    
maxH=max(H)
maxW=max(W)

mh=[i for i,v in enumerate(H) if v==maxH]
mw=[i for i,v in enumerate(W) if v==maxW]

for i in mh :
    for j in mw :
        if [i,j] not in HW :
            print(maxH+maxW)
            exit()
print(maxH+maxW-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
mp =  [[0 for i in range(h)] for j in range(w)]
for i in range(m):
  l =list(map(int, input().split()))
  mp[l[1]-1][l[0]-1] = 1
mx = 0
for y in range(w):
  for x in range(h):
    cn = 0
    for xx in range(h):
      cn += mp[y][xx]
    for yy in range(w):
      if yy != y:
        cn += mp[yy][x]
    if cn > mx:
      mx = cn
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W, M = MI()
    Hlist = [[0, i] for i in range(H)]
    Wlist = [[0, i] for i in range(W)]
    Dlist = [[] for i in range(H)]
    H_max = -float('inf')
    W_max = -float('inf')
    
    for i in range(M):
        h, w = MI()
        Hlist[h-1][0]+=1
        Wlist[w-1][0]+=1
        Dlist[h-1].append(w-1)
        H_max = max(H_max, Hlist[h-1][0])
        W_max = max(W_max, Wlist[w-1][0])
    Hlist = [temp for temp in Hlist if temp[0] == H_max]
    Wlist = [temp for temp in Wlist if temp[0] == W_max]
    ans = H_max+W_max-1

    for num1, index1 in Hlist:
        for num2, index2 in Wlist:
            if not index2 in Dlist[index1]:
                ans = num1+num2
                break
        else:
            continue
        break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
mp =  [[0 for i in range(h)] for j in range(w)]
for i in range(m):
  l =list(map(int, input().split()))
  mp[l[1]-1][l[0]-1] = 1
#print(mp)

mx = 0
for y in range(w):
  for x in range(h):
    cn = 0
#    print('xy',x,y)
    #X軸について
    for xx in range(h):
      cn += mp[y][xx]
#      print(y,xx,mp[y][xx])
    #Y軸について
    for yy in range(w):
      if yy != y:
        cn += mp[yy][x]
#        print(yy,x,mp[yy][x])
    if cn > mx:
      mx = cn
#    print('mx',y,x,mx)
print(mx)

Submission status: Time Limit Exceeded

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

row = [ 0 for _ in range(h)]
col = [ 0 for _ in range(w)]
pos = []

for _ in range(m):
    py, px = map(int, input().split())
    row[py - 1] += 1
    col[px - 1] += 1
    pos.append([py - 1, px - 1])

rmax = max(row)
cmax = max(col)

cross_c = 0
rcand = [i for i in range(h) if row[i] == rmax]
ccand = [i for i in range(w) if col[i] == cmax]
for r, c in pos:
    if r in rcand and c in ccand:
        cross_c += 1

if len(rcand) * len(ccand) > cross_c:
    print(rmax + cmax)
else:
    print(rmax + cmax - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
map = [[False]*W for _ in range(H)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
    map[h-1][w-1] = True
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

cnt = len(hs)*len(ws)
for h in hs:
    for w in ws:
        if not map[h][w]:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)

Submission status: Time Limit Exceeded

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

cnt_dict_h = {}
cnt_dict_w = {}
bomb_list = []

for i in range(M):
    h, w = [int(i)-1 for i in input().split()]
    bomb_list.append((h,w))
    cnt_dict_h.setdefault(h, 0)
    cnt_dict_h[h] += 1
    cnt_dict_w.setdefault(w, 0)
    cnt_dict_w[w] += 1

max_h_key_list = [kv[0] for kv in cnt_dict_h.items() if kv[1] == max(cnt_dict_h.values())]
max_w_key_list = [kv[0] for kv in cnt_dict_w.items() if kv[1] == max(cnt_dict_w.values())]
max_h = max(cnt_dict_h.values())
max_w = max(cnt_dict_w.values())

bomb_num = max_h + max_w - 1

flag = False

for h in max_h_key_list:
    for w in max_w_key_list:
        if (h, w) not in bomb_list:
            bomb_num = max_h + max_w
            break
        else :
            continue
        break
        
print(bomb_num)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = list(map(int,input().split()))
import numpy as np
targets = []
lines = [0]*(H+1)
rows = [0]*(W+1)
for i in range(M):
    l,r = list(map(int,input().split()))
    targets.append((l,r))
    lines[l] += 1
    rows[r] += 1
lmax = max(lines)
rmax = max(rows)
lmax_cand = [i for i in range(H+1) if lines[i] == lmax]
rmax_cand = [i for i in range(W+1) if rows[i] == rmax]
res = 0
import sys
for ll in lmax_cand:
    for rr in rmax_cand:
        if (ll,rr) not in targets:
            res = lmax + rmax
            print(res)
            sys.exit()
        else:
            res = max(res,lmax+rmax-1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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())
ch = Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in zip(h,w):
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int, input().split())
arr = [[0 for _ in range(b)] for _ in range(a)]
for _ in range(c):
    x,y = map(int, input().split())
    arr[x-1][y-1] = '#'

ans = 0
for i in range(a):
    for j in range(b):
        if arr[i][j] == '#':
            ans = max(ans, (arr[i].count('#')+list(zip(*arr))[j].count('#'))-1)
        else:
            ans = max(ans, arr[i].count('#')+list(zip(*arr))[j].count('#'))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
hb= [[0, i+1] for i in range(h)]
wb=[[0, i+1] for i in range(w)]
bo=[]
for i in range(m):
    a,b=list(map(int, input("").split()))
    hb[a-1][0]+=1
    wb[b-1][0]+=1
    bo.append([a,b])
list.sort(hb, reverse=True)
list.sort(wb, reverse=True)
mwb=[]
mhb=[]
for i in hb:
    if i[0]==hb[0][0]:
        mhb.append(i[1])
    else:
        break
for i in wb:
    if i[0]==wb[0][0]:
        mwb.append(i[1])
    else:
        break
c=0
for h,w in bo:
    if h in mhb and w in mwb:
        c+=1
out=hb[0][0]+wb[0][0]
if c==len(mwb)*len(mhb):
    out-=1

print(out)

Submission status: Time Limit Exceeded

Solution code:
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 T in range(M):
    if c[T][0] in leftkeys and c[T][1] in rightkeys:
        cnt = cnt + 1
    else:
        pass
 
 
if cnt == int(leftkeyN * rightkeyN):
    print(int(tempmax - 1))
else:
    print(int(tempmax))

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int,input().split())
bomb = [0] * m
list_h = [0] * h #行ごとの爆破対象数
list_w = [0] * w #列ごとの爆破対象数
for i in range(m):
  bomb[i] = list(map(int,input().split()))
for i in range(m):
  list_h[bomb[i][0]-1] += 1
  list_w[bomb[i][1]-1] += 1
ans = 0
for i in range(h):
  for j in range(w):
    sum = list_h[i] + list_w[j]
    if [i+1,j+1] in bomb:
      sum -= 1
    ans = max(ans,sum)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

cnt = len(hs)*len(ws)
for h, w in HW:
    if h-1 in hs and w-1 in ws:
        cnt -= 1
print(max(h_count)+max(w_count) - (cnt==0))

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
lsh = [0] * h
lsw = [0] * w

bom = []
for _ in range(m):
    m1, m2 = map(int, input().split())
    lsh[m1 - 1] += 1
    lsw[m2 - 1] += 1
    bom.append((m1-1, m2-1))
#print(lsh)
#print(lsw)

lshmax = max(lsh)
lswmax = max(lsw)

jd= False

for i in range(h):
    if lsh[i] == lshmax:
        for j in range(w):
            if lsw[j] == lswmax:
                if (i, j) not in bom:
                    jd= True
                    #print(i,j)
if jd:
    print(lshmax+lswmax)
else:
    print(lshmax + lswmax -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W, M = MI()
    Hlist = [[0, i] for i in range(H)]
    Wlist = [[0, i] for i in range(W)]
    Dlist = [[] for i in range(H)]
    H_max = -float('inf')
    W_max = -float('inf')
    
    for i in range(M):
        h, w = MI()
        Hlist[h-1][0]+=1
        Wlist[w-1][0]+=1
        Dlist[h-1].append(w-1)
        H_max = max(H_max, Hlist[h-1][0])
        W_max = max(W_max, Wlist[w-1][0])
    Hlist = [temp for temp in Hlist if temp[0] == H_max]
    Wlist = [temp for temp in Wlist if temp[0] == W_max]
    ans = -float('inf')
    for num1, index1 in Hlist:
        for num2, index2 in Wlist:
            if index2 in Dlist[index1]:
                ans = max(ans, num1+num2-1)
            else:
                ans = max(ans, num1+num2)
                break
        else:
            continue
        break
                
            
    print(ans)
            

if __name__ == "__main__":
    main()

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(i for i in range(len(hl)) if hl[i]==hlmax)
wlidx = tuple(i for i in range(len(wl)) if wl[i]==wlmax)
minus = 1
if len(hlidx)*len(wlidx)>len(hw): minus=0
# else:
#     for i in hlidx:
#         for j in wlidx:
#             if not [i+1,j+1] in hw:
#                 minus=0
#                 break
fltd = tuple(a for a in hw if a[0]-1 in hlidx and a[1]-1 in wlidx)
if len(fltd)!=len(hlidx)*len(wlidx): minus=0
#print(fltd,hw)
# for i in hlidx:
#     for j in wlidx:
# #        print([i+1,j+1],fltd)
#         if not [i+1,j+1] in fltd:
#             minus=0
#             break
print(max(hl)+max(wl)-minus)

Submission status: Time Limit Exceeded

Solution code:
#import random

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

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append([])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=putmx(wb,mwb)

#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:
H, W, M = map(int, input().split())
cntH = {}
cntW = {}
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb.add((h-1,w-1))
    cntH[h-1] = cntH.get(h-1, 0) + 1
    cntW[w-1] = cntW.get(w-1, 0) + 1

max_H_list = [kv[0] for kv in cntH.items() if kv[1] == max(cntH.values())]
max_W_list = [kv[0] for kv in cntW.items() if kv[1] == max(cntW.values())]
ans = max(cntH.values()) + max(cntW.values())

flag = False
for i in max_H_list:
    for j in max_W_list:
        if (i, j) not in bomb:
            flag = True
            break
    else:
        continue
    break
if not flag:
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

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

row = [ 0 for _ in range(h)]
col = [ 0 for _ in range(w)]
pos = []

for _ in range(m):
    py, px = map(int, input().split())
    row[py - 1] += 1
    col[px - 1] += 1
    pos.append([py - 1, px - 1])

rmax = max(row)
cmax = max(col)

cross_c = 0
rcand = [i for i, x in enumerate(row) if x == rmax]
ccand = [i for i, x in enumerate(col) if x == cmax]
for b in pos:
    if b[0] in rcand and b[1] in ccand:
        cross_c += 1

if len(rcand) * len(ccand) > cross_c:
    print(rmax + cmax)
else:
    print(rmax + cmax - 1)

Submission status: Time Limit Exceeded

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

bombw = [0]*w
bombh = [0]*h
bomb = []
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    bomb.append([str(hi-1)+"-"+str(wi-1)])
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if [str(i)+"-"+str(j)] not in bomb:
            print(ans)
            exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
gyou=[]
retsu=[]
goukei=[]
for i in range(m):
    a,b = map(int,input().split())
    gyou.append(a)
    retsu.append(b)
    goukei.append([a,b])
import collections
gyoucounted = collections.Counter(gyou)
gyoulist = [gyou for gyou,count in gyoucounted.most_common() if count == gyoucounted.most_common()[0][1]]
gkosuu=gyoucounted.most_common()[0][1]


retsucounted = collections.Counter(retsu)
retsulist = [retsu for retsu,count in retsucounted.most_common() if count == retsucounted.most_common()[0][1]]
rkosuu=retsucounted.most_common()[0][1]

judge=0
for i in gyoulist:
    for j in retsulist:
        if [i,j] not in goukei:
            judge=1
            break
if judge==1:
    print(gkosuu+rkosuu)
else:
    print(gkosuu+rkosuu-1)

Submission status: Time Limit Exceeded

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

row = [ 0 for _ in range(h)]
col = [ 0 for _ in range(w)]
pos = []

for _ in range(m):
    py, px = map(int, input().split())
    row[py - 1] += 1
    col[px - 1] += 1
    pos.append([py - 1, px - 1])

rmax = max(row)
cmax = max(col)

cross_c = 0
rcand = [i for i, x in enumerate(row) if x == rmax]
ccand = [i for i, x in enumerate(col) if x == cmax]
for r in rcand:
    for c in ccand:
        if [r, c] in pos:
            cross_c += 1

if len(rcand) * len(ccand) > cross_c:
    print(rmax + cmax)
else:
    print(rmax + cmax - 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools
from collections import defaultdict
import numpy as np


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    H, W, M = list(map(int, input().split()))
    B = []
    I = defaultdict(int)
    R = defaultdict(int)
    for m in range(M):
        h_m, w_m = list(map(int, input().split()))
        B.append((h_m, w_m))
        I[h_m] += 1
        R[w_m] += 1

    return H, W, M, B, I, R


def main(H: int, W: int, M: int, B: list, I: dict, R: dict) -> None:
    """
    メイン処理.

    Args:\n
        H (int): 行数(1 <= H <= 3 * 10**5)
        W (int): 列数(1 <= W <= 3 * 10**5)
        M (int): 爆破対象数(1 <= M <= min(H * W, 3 * 10**5))
        B (list): 爆破対象の位置
        I (dict): 行ごとの爆破対象数
        R (dict): 列ごとの爆破対象数
    """
    # 求解処理
    max_bom_h = max(I.values())
    h_bom = [k for k, v in I.items() if v == max_bom_h]

    max_bom_w = max(R.values())
    w_bom = [k for k, v in R.items() if v == max_bom_w]

    can_separate = False
    for h_b, w_b in itertools.product(h_bom, w_bom):
        if (h_b, w_b) not in B:
            can_separate = True
            break

    ans = max_bom_h + max_bom_w
    if not can_separate:
        ans -= 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    H, W, M, B, I, R = get_input()

    # メイン処理
    main(H, W, M, B, I, R)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
(H,W,M) = map(int, input().split())
hsum = [0]*H
wsum = [0]*W
bombs = set()
for _ in range(M):
    h,w = map(int, input().split())
    hsum[h-1] += 1
    wsum[w-1] += 1
    bombs.add((h-1,w-1))

hmax = max(hsum)
wmax = max(wsum)

cross_w_zero = False
for h in range(H):
    if hsum[h] == hmax:
        for w in range(W):
            if wsum[w] == wmax and (h,w) not in bombs:
                cross_w_zero = True
                break
    if cross_w_zero:
        break
if cross_w_zero:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
(H,W,M) = map(int, input().split())
hsum = [0]*H
wsum = [0]*W
bombs = set()
for _ in range(M):
    h,w = map(int, input().split())
    hsum[h-1] += 1
    wsum[w-1] += 1
    bombs.add((h-1,w-1))

hmax = max(hsum)
wmax = max(wsum)

cross_w_zero = False
for h in range(H):
    if hsum[h] == hmax:
        for w in range(W):
            if wsum[w] == wmax and (h,w) not in bombs:
                cross_w_zero = True
                break
    if cross_w_zero:
        break
if cross_w_zero:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

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

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append([])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=putmx(wb,mwb)

#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:
h,w,m=map(int, input().split())
r = [0]*max(h,w)
c = [0]*max(h,w)
l=[]

for i in range(m):
    x,y=map(int, input().split())
    r[x-1]+=1
    c[y-1]+=1
    l.append([x,y])

cm = max(c)
rm = max(r)
ci = [i for i, x in enumerate(c) if x == cm]
ri = [i for i, x in enumerate(r) if x == rm]
ans = cm + rm

cnt = 0
#print(l,ci,ri)
for i in range(m):
    if l[i][0]-1 in ri and l[i][1]-1 in ci:
        cnt += 1

if cnt == len(ci)*len(ri):
    print(int(ans)-1)
else:
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
bh = []
bw = []
l_num = [0]*h
c_num = [0]*w
for i in range(m):
    i1, i2 = map(int, input().split())
    bh.append(i1)
    bw.append(i2)
    l_num[i1-1] = l_num[i1-1] + 1
    c_num[i2-1] = c_num[i2-1] + 1

#print(l_num,c_num)

l_candi = [i for i, v in enumerate(l_num) if v == max(l_num)]
c_candi = [i for i, v in enumerate(c_num) if v == max(c_num)]

#print(l_candi,c_candi)

t = 0
for k in range(m):
    if bh[k]-1 in l_candi and bw[k]-1 in c_candi:
        t = t + 1

if t < len(l_candi)*len(c_candi):
    print(max(l_num)+max(c_num))
else:
    print(max(l_num)+max(c_num)-1)

Submission status: Time Limit Exceeded

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

targets = []
h_count = [0] * H
w_count = [0] * W

for _ in range(M):
    targets.append([int(v) - 1 for v in input().split()])

for x, y in targets:
    h_count[x] += 1
    w_count[y] += 1

h_count_max = max(h_count)
w_count_max = max(w_count)

h_max_idx = [i for i, x in enumerate(h_count) if x == h_count_max]
w_max_idx = [i for i, x in enumerate(w_count) if x == w_count_max]

flag = False
for h in h_max_idx:
    for w in w_max_idx:
        if [h, w] not in targets:
            flag = True
            break

    if flag:
        break


ans = h_count_max + w_count_max
if not flag:
    ans -= 1

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
if len(hlidx)*len(wlidx)>len(hw): minus=0
# else:
#     for i in hlidx:
#         for j in wlidx:
#             if not [i+1,j+1] in hw:
#                 minus=0
#                 break
fltd = tuple(filter(lambda a:a[0]-1 in hlidx and a[1]-1 in wlidx,hw))
if len(fltd)!=len(hlidx)*len(wlidx): minus=0
#print(fltd,hw)
# for i in hlidx:
#     for j in wlidx:
# #        print([i+1,j+1],fltd)
#         if not [i+1,j+1] in fltd:
#             minus=0
#             break
print(max(hl)+max(wl)-minus)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def get_keys_of_max_value(d):
    v_max = 0
    keys = []
    for k, v in d.items():
        if v_max < v:
            v_max = v
            keys = [k]
        elif v_max == v:
            keys.append(k)
    return keys, v_max

h, w, m = map(int, input().split())
targets = [tuple(map(int, input().split())) for _ in range(m)]
n_r = defaultdict(int)
n_c = defaultdict(int)
for x, y in targets:
    n_r[x] += 1
    n_c[y] += 1

rows, n_r_max = get_keys_of_max_value(n_r)
columns, n_c_max = get_keys_of_max_value(n_c)

for r in rows:
    for c in columns:
        if (r, c) not in targets:
            print(n_r_max + n_c_max)
            break
    else:
        continue
    break
else:
    print(n_r_max + n_c_max - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = list(map(int,input().split()))
import numpy as np
targets = []
lines = [0]*(H+1)
rows = [0]*(W+1)
for i in range(M):
    l,r = list(map(int,input().split()))
    targets.append((l,r))
    lines[l] += 1
    rows[r] += 1
lmax = max(lines)
lmax_cand = []
rmax = max(rows)
rmax_cand = []
for i in range(H+1):
    if lines[i] == lmax:
        lmax_cand.append(i)
for i in range(W+1):
    if rows[i] == rmax:
        rmax_cand.append(i)
res = 0
for ll in lmax_cand:
    for rr in rmax_cand:
        if (ll,rr) in targets:
            res = max(res,lmax+rmax-1)
        else:
            res = lmax+rmax
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
def main():
    H,W,M = map(int,input().split())
    h = [[0,i] for i in range(H)]
    w = [[0,i] for i in range(W)]
    HW = [[0 for j in range(W)]for i in range(H)]
    HW = np.array(HW)
    for i in range(M):
        tmp = list(map(int,input().split()))
        tmp_0 = tmp[0]-1
        tmp_1 = tmp[1]-1
        h[tmp_0][0] += 1
        w[tmp_1][0] += 1
        HW[tmp_0][tmp_1] += 10
    
    list.sort(h, reverse=True)
    list.sort(w, reverse=True)
    max_h = h[0][0]
    max_w = w[0][0]
    ans = max_h + max_w
    for i in range(len(h)):
        if h[i][0] < max_h:
            break
        HW[h[i][1]] += 1
        
    for i in range(len(w)):
        if w[i][0] < max_w:
            break
        HW[:,w[i][1]] += 1
    
    if 2 not in HW:
        ans -= 1
    
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

h_value = [0]*(H+1)
w_value = [0]*(W+1)
exist = [ [0 for _ in range(W+1)] for _ in range(H+1)]
for coordinate in hw:
    h_value[coordinate[0]] += 1
    w_value[coordinate[1]] += 1
    exist[coordinate[0]][coordinate[1]] = 1

h_max = max(h_value)
w_max = max(w_value)

h_max_ind = list()
w_max_ind = list()
h_max_ind_exist = [0]*(H+1)
w_max_ind_exist = [0]*(W+1)

for i in range(H+1):
    if h_value[i] == h_max:
        h_max_ind.append(i)
        h_max_ind_exist[i] = 1


for i in range(W+1):
    if w_value[i] == w_max:
        w_max_ind.append(i)
        w_max_ind_exist[i] = 1

# print("put", h_max_ind, w_max_ind)
flag = False
if len(h_max_ind)*len(w_max_ind) > M:
    flag = True
else:
    for h in h_max_ind:
        for w in w_max_ind:
            if exist[h][w] == 0:
                flag = True

if flag:
    print(h_max + w_max)
else:
    print(h_max + w_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b,c=[0]*h,[0]*w
for t1,t2 in a:
    b[t1-1]+=1
    c[t2-1]+=1
bm,cm=max(b),max(c)
b1,c1=[],[]
d=[]
for x,y in a:
    d.append((x-1,y-1))
d=set(d)
for i in range(h):
    if b[i]==bm:
        b1.append(i)
for i in range(w):
    if c[i]==cm:
        c1.append(i)
f=1
for i in b1:
    for j in c1:
        if (i,j) not in d:
            f=0
print(bm+cm-f)

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)]

max_h = 0
max_w = 0
h_indices = []
w_indices = []

for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    if bomb_h[h-1] == max_h:
        h_indices.append(h-1)
    elif bomb_h[h-1] > max_h:
        h_indices = [h-1]
        max_h = bomb_h[h-1]

    if bomb_w[w-1] == max_w:
        w_indices.append(w-1)
    elif bomb_w[w-1] > max_w:
        w_indices = [w-1]
        max_w = bomb_w[w-1]

    grid[h-1][w-1] = True

ans = max_w + max_h - 1
assert(len(h_indices) * len(w_indices) < 100000000)

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)