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 numpy as np
import collections
#import math




#f = open('./input_E.txt')
#
#H,W,M=map(int, f.readline().split())
#bakuha = []
#bakuha_H=[]
#bakuha_W=[]
#for i in range(M):
#    hh,ww=map(int, f.readline().split())
#    bakuha_H.append(hh)
#    bakuha_W.append(ww)
#    bakuha.append([hh,ww])



#
H,W,M=map(int, input().split())
bakuha = []
bakuha_H=[]
bakuha_W=[]
for i in range(M):
    hh,ww=map(int, input().split())
    bakuha_H.append(hh)
    bakuha_W.append(ww)
    bakuha.append([hh,ww])





count_H = collections.Counter(bakuha_H)
H_most = count_H.most_common()
H_most_num = H_most[0][1]

H_only_most = [x for x in H_most if x[1]==H_most_num]
H_kouho = [x[0] for x in H_only_most]


count_W = collections.Counter(bakuha_W)
W_most = count_W.most_common()
W_most_num = W_most[0][1]

W_only_most = [x for x in W_most if x[1]==W_most_num]
W_kouho = [x[0] for x in W_only_most]

ans = H_most_num + W_most_num

len_H_kouho =len(H_kouho)
len_W_kouho = len(W_kouho) 
num_kouho = len_H_kouho*len_W_kouho
if num_kouho <= M:
    if len_H_kouho<=len_W_kouho:
        kouho = [x for x in bakuha if x[0] in H_kouho]
        kouho = [x for x in kouho if x[1] in W_kouho]
    else:
        kouho = [x for x in bakuha if x[1] in W_kouho]
        kouho = [x for x in kouho if x[0] in H_kouho]        
#    kouho = [x for x in bakuha if x[0] in H_kouho and x[1] in W_kouho]
    if len(kouho) == len(H_kouho)*len(W_kouho):
        ans-=1

#ryouhou = 0
#for bb in bakuha:
#    x,y = bb
#    if x in H_kouho and y in W_kouho:
#        ryouhou+=1
#
#h_by_w = len(H_kouho)*len(W_kouho)
#
#if ryouhou == h_by_w:
#    ans -= 1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for _ in range(M):
    P.append(list(map(int,input().split())))
for m in range(M):
    P_X[P[m][0]]+=1
for m in range(M):
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
max_list=list()
for i, j in itertools.product(max_X, max_Y):
    max_list.append([i,j])
m_count=0
for k in range(M):
    if P[k] in max_list:
        m_count += 1
if m_count==len(max_list):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
ans=0
t=max(hh)[0]
for j in w:
  for x,i in sorted(hh,reverse=1):
    if x!=t:break
    if (i,j) in hw:
      ans=s+x-1
    else:
      exit(print(s+x))
print(ans)

Submission status: Time Limit Exceeded

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

H, W, M = map(int, input().split())
tate = []
yoko = []
S = []

for i in range(M):
    h, w = map(int, input().split())
    tate.append(h-1)
    yoko.append(w-1)
    S.append([h-1, w-1])

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in range(len(yoko_index)):
    for j in range(len(tate_index)):
        if [tate_index[j], yoko_index[i]] in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys
    input = sys.stdin.readline
    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(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[y][x] = 1
        
    kouho_h = []
    kouho_w = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    for i in kouho_h:
        for j in kouho_w:
            if bomb[i][j] == False:
                print(max_h + max_w)
                exit()
    print(max_h + max_w - 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
A=[[0]*H]*W
Bomb_ls=[]
X=[0]*M
Y=[0]*M
for i in range(M):
  X[i],Y[i]=[int(x) for x in input().split()]
  Bomb_ls.append([X[i],Y[i]])
R=Counter(X)
C=Counter(Y)
R_max = [letter for letter,count in R.most_common() if count == R.most_common()[0][1]]
C_max = [letter for letter,count in C.most_common() if count == C.most_common()[0][1]]
score=-1
for r in R_max:
  for c in C_max:
    if not [r,c] in Bomb_ls:
      score=0
      break
  else:
    continue
  break
print(max(R.values())+max(C.values())+score)

Submission status: Time Limit Exceeded

Solution code:
import numpy

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

area = []
w_list = []

max = 0


for i in range(h):
    w_list = []
    for j in range(w):
        w_list.append(".")

    area.append(w_list)

for num in range(m):
    t_h, t_w = map(int, input().split())

    area[t_h-1][t_w-1] = "#"

np_area = numpy.array(area)

for i in range(h):
    for j in range(w):
        count = 0
        yoko = np_area[i]
        tate = np_area[:, j]

        count += len(numpy.where(yoko =="#")[0])
        count += len(numpy.where(tate == "#")[0])
        if area[i][j] == "#":
            count -= 1

        if count > max:
            max = count


print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=[[] for i in range(h+1)]
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    hd2[h0].append(w0)
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    
max_h_list=[]
max_w_list=[]
for k in hd.keys():
    if hd[k]==hmax:
        max_h_list.append(k)

for k in wd.keys():
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hmax+wmax-ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
HW = set()
hd = {}
wd = {}
for i in range(M):
	h, w = tuple(map(int, input().split()))
	HW.add((h, w))
	if h in hd:
		hd[h] += 1
	else:
		hd[h] = 1
	if w in wd:
		wd[w] += 1
	else:
		wd[w] = 1

hm = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
wm = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]
ans = 0
for h in hm:
	for w in wm:
		if (h, w) in HW:
			ans = max(ans, (hd[h] + wd[w] - 1))
		else:
			ans = max(ans, (hd[h] + wd[w]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
s = [0]*h
t = [0]*w
u = []
x = 0
for i in range(m):
    a,b = map(int,input().split())
    s[a-1] += 1
    t[b-1] += 1
    u.append([a-1,b-1])
if(h == 1 or w == 1):
    print(m)
else:
    p = max(s)
    q = max(t)
    r = []
    for i in range(h):
        if(s[i] == p):
            r.append(i)
    v = []
    for i in range(w):
        if(t[i] == q):
            v.append(i)
    for i in range(len(r)):
        for j in range(len(v)):
            if([r[i],v[j]] not in u):
                x = 1
                break
    if(x == 1):
        print(p+q)
    else:
        print(p+q-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]

    bh_destroy = bomb_most_h[1]
    bw_destroy = bomb_most_w[1]
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    ans = bh_destroy+bw_destroy
    
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if not([bh,bw] in BOMB_HW):
                print(ans)
                sys.exit()
    print(ans-1)
    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def main():
    h, w, m = [int(i) for i in input().split()]
    d_h = defaultdict(int)
    d_w = defaultdict(int)
    bom = set()
    for _ in range(m):
        h, w = [int(i) for i in input().split()]
        bom.add((h, w))
        d_h[h] += 1
        d_w[w] += 1
    ans = 0
    for k_h, v_h in d_h.items():
        for k_w, v_w in d_w.items():
            tmp = v_h + v_w
            if (k_h, k_w) in bom:
                tmp -= 1
            ans = max(ans, tmp)

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_hw = [[] for _ in range(h+1)]

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_hw[h].append(w)

m_h = max(l_h)
m_w = max(l_w)

ans = m_h + m_w

l_h_2 = my_index_multi(l_h,m_h)
l_w_2 = my_index_multi(l_w,m_w)


for i,j in itertools.product(l_h_2,l_w_2):
    if j not in l_hw[i]:
        break
else:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    regy = [0]*h
    regx = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        regy[x[0]] += 1
        regx[x[1]] += 1
        c[x[0]][x[1]] = 1
    maxy = 0
    indy = []
    for i in range(h):
        if maxy < regy[i]:
            indy = [i]
            maxy = regy[i]
        elif maxy == regy[i]:
            indy.append(i)
    maxx = 0
    indx = []
    for i in range(w):
        if maxx < regx[i]:
            indx = [i]
            maxx = regx[i]
        elif maxx == regx[i]:
            indx.append(i)

    ans = maxy + maxx
    tmp = 1
    if len(indy)*len(indx) > m:
        tmp = 0
    else:
        for y in indy:
            for x in indx:
                if c[y][x] == 0:
                    tmp = 0
    print(ans - tmp)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=[[] for i in range(h+1)]
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

hmax=max(hd.values())
wmax=max(wd.values())
max_h_list=[]
max_w_list=[]
for k in hd.keys():
    if hd[k]==hmax:
        max_h_list.append(k)

for k in wd.keys():
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hmax+wmax-ans)

Submission status: Time Limit Exceeded

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

H=[0]*h
W=[0]*w
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

ok=0
for mine in M:
    if mine[0]-1 in maxhindex and mine[1]-1 in maxwindex:
        ok+=1

ans=maxh+maxw
if ok==len(maxhindex)*len(maxwindex):
    ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
h, w, m = map(int, input().split())
r = [0] * h
c = [0] * w
s = set()
for _ in range(m):
    x, y = map(lambda i: int(i) - 1, input().split())
    r[x] += 1
    c[y] += 1
    s.add((x, y))
R = max(r)
C = max(c)
ans = {(i, j)
       for i, p in enumerate(r) for j, q in enumerate(c) if p == R and q == C}
print(R + C - (len(ans - (ans & s)) == 0))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
HW_L = [[int(x)-1 for x in input().split()] for y in range(M)]

w_l = [0] * W
h_l = [0] * H

for _hi, _wi in HW_L:
    w_l[_wi] += 1
    h_l[_hi] += 1

max_h = max(h_l)
max_w = max(w_l)

h_idx = [i for i, x in enumerate(h_l) if x == max_h]
w_idx = [i for i, x in enumerate(w_l) if x == max_w]

ans = max_h + max_w - 1

for hi in h_idx:
    for wj in w_idx:
        if [hi, wj] not in HW_L:
            ans = max_h + max_w
            break
    else:
        continue
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  H,W,m=map(int,input().split())
  h=np.zeros(H, dtype = int)
  w=np.zeros(W, dtype = int)
  hw={}
  for i in range(m):
    hi,wi=map(int,input().split())
    hi=hi-1
    wi=wi-1
    h[hi]+=1
    w[wi]+=1
    hw[(hi,wi)]=0
  yn=1
  hm=np.max(h)
  wm=np.max(w)
  #print(hw)
  for j in range(H):
    if h[j]==hm:
      #print(h)
      for k in range(W):
        if w[k]==wm:
          #print(k)
          #print(hw[3,k])
          if (j,k) not in hw:
            yn=0
            break
      else:
        continue
      break
  print(hm+wm-yn)
main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=set()
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.add((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:
import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
B=set()

for i in range(M):
    hi,wi=map(int, input().split())
    #h.append(hi)
    #w.append(wi)
    B.add((hi,wi))
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        if (h_max[ii]+1,w_max[jj]+1) not in B:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * 2 for i in range(M)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[i] = [hi-1, wi-1]

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]

tmp = M
for i in range(M):
    if (DST[i][0] not in Hbomb) or (DST[i][1] not in Wbomb):
        tmp -= 1

if len(Hbomb)*len(Wbomb) == tmp:
    print(Hdstmax + Wdstmax - 1)
else:
    print(Hdstmax + Wdstmax)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

hmax=max(hd.values())
wmax=max(wd.values())
max_h_list=[]
max_w_list=[]
for k in hd.keys():
    if hd[k]==hmax:
        max_h_list.append(k)

for k in wd.keys():
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hmax+wmax-ans)

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
    hw = []

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


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

    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1
    if count != len(hmax) * len(wmax):
        flag = True

    if flag:
        print(Hlist[hmax[0]] + Wlist[wmax[0]])
    else:
        print(Hlist[hmax[0]] + Wlist[wmax[0]] - 1)





if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

wl = [0]*W
hl = [0]*H

for m in range(M):
    hn = obj[m][0]-1
    wn = obj[m][1]-1
    hl[hn] = hl[hn] + 1
    wl[wn] = wl[wn] + 1
    
mhl = [a for a, b in enumerate(hl) if b == max(hl)]
mwl = [a for a, b in enumerate(wl) if b == max(wl)]

for d in range(len(mhl)):
    for e in range(len(mwl)):
        if [mhl[d]+1,mwl[e]+1] in obj:
            continue
        else:
            print(int(max(hl)+max(wl)))
            sys.exit()
print(int(max(hl)+max(wl)-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    row_bombers = [0] * (H+1)
    col_bombers = [0] * (W+1)

    for (h, w) in hw:
        row_bombers[h] += 1
        col_bombers[w] += 1

    row_max = max(row_bombers)
    col_max = max(col_bombers)

    max_rows = [i for i in range(H+1) if row_bombers[i] == row_max]
    max_cols = [i for i in range(W+1) if col_bombers[i] == col_max]

    ans = row_max + col_max
    
    num_empty_cells_in_kouho = len(max_rows) * len(max_cols)
    for (h, w) in hw:
        if h in max_rows and w in max_cols:
            num_empty_cells_in_kouho -= 1

    if num_empty_cells_in_kouho == 0:
        ans -= 1
    
    print(ans)


if __name__ == '__main__':
    main()

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<=300000:
    for s in range(zzx):
        ss=lmx[s]
        if zzz==0:
            break
        for t in range(zzy):
            tt=lmy[t]
            uu=tt*h+ss
            if zzz==0:
                break
            if uu not in mp:
                zzz=0
                break
else:
    zzz=0
print(mx+my-zzz)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
l=[]
out=0
o=0
hb=[]
wb=[]
for i in range(h):
    hb.append([0,i+1])
for i in range(w):
    wb.append([0,i+1])

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)
for i in hb:
    if i[0] !=hb[0][0]:
        break
    for j in wb:
        if j[0] !=wb[0][0]:
            break
        o=i[0]+j[0]
        if [i[1],j[1]] in bo:
            o-=1

        if o>out:
            out=o
print(out)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
#boms = [[0,0] for i in range(m)]
bomh =[0] * m
bomw =[0] * m
Hs = [0] * h
Ws = [0] * w
for i in range(m):
  _h, _w = map(int, input().split())
  #boms[i][0] = _h - 1
  #boms[i][1] = _w - 1
  bomh[i] = _h-1
  bomw[i] = _w-1
  Hs[_h - 1] += 1
  Ws[_w - 1] += 1
Hmax = max(Hs)
Hcount = Hs.count(Hmax)
Wmax = max(Ws)
Wcount = Ws.count(Wmax)
Hindexs = [0] * Hcount
Windexs = [0] * Wcount
hcount = 0
wcount = 0
for i in range(h):
  if Hs[i] == Hmax:
    Hindexs[hcount] = i
    hcount += 1
for i in range(w):
  if Ws[i] == Wmax:
    Windexs[wcount] = i
    wcount += 1
count = 0
for i in range(m):
  if (bomh[i] in Hindexs) and (bomw[i] in Windexs):
    count += 1
# for bom in boms:
#   if (bom[0] in Hindexs) and (bom[1] in Windexs):
if count == len(Hindexs) * len(Windexs):
  print(Hmax + Wmax - 1)
else:
  print(Hmax + Wmax)

Submission status: Time Limit Exceeded

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

def main():
    inputs = list(map(lambda x: int(x), input().split(' ')))
    
    height = {}
    width = {}
    bombs = []

    for i in range(inputs[2]):
        h, w = tuple(map(lambda x :int(x), input().split(' ')))
        bombs.append([h, w])
        if not h in height:
            height[h] = 0
        if  not w in width:
            width[w] = 0
        height[h] += 1
        width[w] += 1

    max_hs = [kv[0] for kv in height.items() if kv[1] == max(height.values())]
    max_ws = [kv[0] for kv in width.items() if kv[1] == max(width.values())]
    max_num = 0
    for hs in max_hs:
        for ws in max_ws:
            if [hs, ws] in bombs:
                num = height[hs] + width[ws] - 1
                if num >= max_num:
                    max_num = num
            else:
                num = height[hs] + width[ws]
                if num >= max_num:
                    max_num = num
    print(max_num)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
l = []

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    l.append((h-1,w-1))
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

maxi = maxh+maxw-1
for i in hlist:
    for j in wlist:
        if (i,j) not in l:
            maxi += 1
            print(maxi)
            exit()
print(maxi)

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_row = max(row_dict.values())
max_col = max(col_dict.values())

max_rows = [k for k, v in row_dict.items() if v == max_row]
max_cols = [k for k, v in col_dict.items() if v == max_col]
ans = max_row + max_col - 1
flg = False
if ans < m:
    for row in max_rows:
        for col in max_cols:
            if not col in row_col_dict[row]:
                ans += 1
                flg = True
                break
        if flg:
            break

print(ans)

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

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 defaultdict as dd
h, w, m = map(int, input().split())

#dic[row, col] -> set(ids)
h_dic = dd(set)
w_dic = dd(set)
spot = set()

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c].add(i)
    w_dic[w_c].add(i)
    spot.add((h_c, w_c))
#print(h_dic, w_dic)

#H_lis -> [i, num_spot(int)]
max_h_num = 0
H_lis = []
for key, val in h_dic.items():
    H_lis.append([key, len(val)])
    max_h_num = max(max_h_num, len(val))
max_w_num = 0
W_lis = []
for key, val in w_dic.items():
    W_lis.append([key, len(val)])
    max_w_num = max(max_w_num, len(val))


#print(H_lis, W_lis)
#print(max_h)

ans = 0
max_h_lis = [val[0] for val in H_lis if val[1] == max_h_num]
max_w_lis = [val[0] for val in W_lis if val[1] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        count = max_h_num + max_w_num
        if (i, j) in spot:
            count -= 1
        ans = max(ans, count)
print(ans)

"""    
max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

"""

Submission status: Time Limit Exceeded

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

targets = []

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

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

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

h_count_max = max(h_count)

max_val = -1

for i in range(H):
    if h_count_max == h_count[i]:
        w_tmp = w_count.copy()

        for x, y in targets:
            if x == i:
                w_tmp[y] -= 1
        
        max_val = max(max_val, max(w_tmp) + h_count_max)

print(max_val)

Submission status: Time Limit Exceeded

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

def solve():
    import sys
    import numpy as np

    H, W, M = list(map(int, sys.stdin.readline().split()))
    grid = np.array([[0 for _ in range(W)] for _ in range(H)])
    for _ in range(M):
        h, w = list(map(int, sys.stdin.readline().split()))
        h, w = h-1, w-1
        grid[h][w] = 1

    cols = np.sum(grid, axis=0)  # 列ごとの合計値
    rows = np.sum(grid, axis=1)  # 行ごとの合計値
    print(cols)
    print(rows)
    print("---")

    ans = np.max(cols) + np.max(rows)
    print(np.max(cols))
    print(np.max(rows))
    print("====")
    col_i = np.argmax(cols)
    row_i = np.argmax(rows)
    print(col_i, row_i)

    if grid[row_i][col_i] == 1:
        print(ans-1)
    else:
        print(ans)

def solve2():
    import sys
    import numpy as np

    H, W, M = list(map(int, sys.stdin.readline().split()))
    grid = np.array([[0 for _ in range(W)] for _ in range(H)])
    for _ in range(M):
        h, w = list(map(int, sys.stdin.readline().split()))
        h, w = h-1, w-1
        grid[h][w] = 1

    L = np.zeros((H,W), dtype=int)
    R = np.zeros((H,W), dtype=int)
    U = np.zeros((H,W), dtype=int)
    D = np.zeros((H,W), dtype=int)

    # 自分より左の爆破数を数える（自分は含めない）
    for w in range(W):
        if w == 0:
            L[:, w] = 0
        else:
            L[:, w] = (L[:, w-1]) + grid[:, w-1]

    # 右の爆破数
    for w in range(W-1, -1, -1):
        if w == W-1:
            R[:, w] = 0
        else:
            R[:, w] = (R[:, w+1]) + grid[:, w+1]

    # 上の爆破数
    for h in range(H):
        if h == 0:
            U[h] = 0
        else:
            U[h] = (U[h-1]) + grid[h-1]

    # 下の爆破数
    for h in range(H-1, -1, -1):
        if h == H-1:
            D[h] = 0
        else:
            D[h] = (D[h+1]) + grid[h+1]

    # 答え
    ans = np.max(L+R+U+D+grid)
    print(ans)



if __name__ == "__main__":
    solve2()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,M = list(map(int, input().split()))
p_list = []
for i in range(M):
    p_list.append(list(map(int, input().split())))

p_array = np.array(p_list)
freq = np.array(np.unique(p_array[:,0], return_counts=True))
H_max = freq[1,:].max()
max_index = np.where(freq[1,:]==H_max)
H_check = freq[0,:][max_index]

freq = np.array(np.unique(p_array[:,1], return_counts=True))
W_max = freq[1,:].max()
max_index = np.where(freq[1,:]==W_max)
W_check = freq[0,:][max_index]

end_flag = False
res = H_max + W_max -1
for i in H_check:
    for j in W_check:
        if [i,j] not in p_list:
            res = H_max + W_max
            end_flag = True
            break
    if end_flag == True:
        break
print(res)