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

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
for r in range(h):
    if row[r] != rmax:
        continue
    for c in range(w):
        if col[c] != cmax:
            continue
        if [r, c] in pos:
            cross_c += 1

if row.count(rmax) * col.count(cmax) == cross_c:
    print(rmax + cmax - 1)
else:
    print(rmax + cmax)

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:
    # 求解処理
    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:
h,w,m=map(int, input().split())
a=[0]*m
hc=[0]*w
wc=[0]*h
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[]
wk=[]
for i in range(len(hc)):
	if hc[i]==hcm:
		hk.extend([i])
for i in range(len(wc)):
	if wc[i]==wcm:
		wk.extend([i])
c=0
for i in range(len(a)):
	if a[i][0] in wk:
		if a[i][1] in hk:
			c+=1
if c==len(hk)*len(wk):
	print(hcm+wcm-1)		
else:
	print(hcm+wcm)

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)
max=[]
for i in range(h) :
    if H[i]==maxH :
        max.append (i)
for i in range(w) :
    if W[i]==maxW :
        for j in max:
            if [j,i] not in HW :
                print(maxH+maxW)
                exit()
print(maxH+maxW-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,M=map(int, input().split())
hl=np.array([0 for i in range(H+1)])
wl=np.array([0 for i in range(W+1)])
ms=[]
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.append([h,w])
a=max(hl)
b=max(wl)
hmax=[]
wmax=[]
for i in range(len(hl)):
    if hl[i]==a:
        hmax.append(i)
for i in range(len(wl)):
    if wl[i]==b:
        wmax.append(i)
# hmax=np.where(hl == hl.max())[0]
# wmax=np.where(wl == wl.max())[0]
bl=False
if len(hmax)*len(wmax)>M:
    bl=True
else:
    for x in hmax:
        for y in wmax:
            if [x,y] not in ms:
                bl=True
                break
        if bl:
            break
if bl:
    print(a+b)
else:
    print(a+b-1)

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

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G.append(i+1)
for i in range(w):
    if r[i]==e:
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = [int(x) for x in input().split()]
hw = []
hNum = [0]*H
wNum = [0]*W

for i in range(M):
    h,w = [int(x) for x in input().split()]
    hw.append([h,w])
    hNum[h-1]+=1
    wNum[w-1]+=1

hmax = max(hNum)
hMaxList = []
wmax = max(wNum)
wMaxList = []

for i in range(H):
    if(hmax == hNum[i]):
        hMaxList.append(i)
for i in range(W):
    if(wmax == wNum[i]):
        wMaxList.append(i)

ans = wmax + hmax
for w in wMaxList:
    for h in hMaxList:
        for k in hw:
            if(not([h+1,w+1] in hw)):
                print(ans)
                exit()
print(ans -1)

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List
import array

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: array[int] = [0] * W
    rowSumList: array[int] = [0] * H

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)]
a=[0 for i in range(h+1)]
b=[0 for _ in range(w+1)]
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a)
bm=max(b)
aa=[i for i, x in enumerate(a) if x==am]
bb=[i for i, x in enumerate(b) if x==bm]
if len(aa)*len(bb)>m:
    print(am+bm)
    exit()
for i in aa:
    for j in bb:
        if [i,j] in bomb:
            continue
        else:
            print(am+bm)
            exit()
print(am+bm-1)

Submission status: Time Limit Exceeded

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

boms=[[0 for j in range(W)] for i in range(H)]
for i in range(M):
  h,w=map(int,input().split())
  boms[h-1][w-1]=1
  row_boms[h-1]+=1
  col_boms[w-1]+=1

row_max=max(row_boms)
col_max=max(col_boms)

rowmax_h=[]
colmax_w=[]
for i in range(H):
  if row_boms[i]==row_max:
    rowmax_h+=[i]
for i in range(W):
  if col_boms[i]==col_max:
    colmax_w+=[i]
rows=len(rowmax_h)
cols=len(colmax_w)
tf=0
for i in rowmax_h:
  for j in colmax_w:
    if boms[i][j]==0:
      tf=1
      break

if tf==1:
  print(row_max+col_max)
else:
  print(row_max+col_max-1)

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = [i+1 for i, h_ in enumerate(h_lst) if h_ == h_count]
w_cand = [i+1 for i, w_ in enumerate(w_lst) if w_ == w_count]
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
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 m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    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)
m_count=0
for k in P:
    if  k[0] in max_X and k [1] in max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = []
for x in range(m):
    H, W = map(int, input().split())
    bomb.append((H-1, W-1))
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)

for i in p:
    for j in q:
        if (i, j) not in bomb:
            print(ans + 1)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import random

def putmx(lis,mx):
  ret=[]
  lis.sort(key=lambda x: x[0],reverse=True)
  for i in lis:
    if i[0]!=mx:
      break
    ret.append(i[1])
  return ret
  

h,w,m=map(int,input().split())
hl=[0]*h
wl=[0]*w
hb=[]
wb=[]
bmb=[]
for i in range(h):
  bmb.append([])
  hb.append([0,i])
for i in range(w):
  wb.append([0,i])
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].append(ww)
  hb[hh][0]+=1
  wb[ww][0]+=1
  hl[hh]+=1
  wl[ww]+=1
mhb=max(hl)
mwb=max(wl)
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:
#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H

    maxColumnSum = 0
    maxColumIndexList: List[int] = []
    maxRowSum = 0
    maxRowIndexList: List[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
boms = []
Hs = [0] * h
Ws = [0] * w
for i in range(m):
  _h, _w = map(int, input().split())
  boms.append((_h - 1,_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 bom in boms:
  if (bom[0] in Hindexs) and (bom[1] in Windexs):
    count += 1
if count == len(Hindexs) * len(Windexs):
  print(Hmax + Wmax - 1)
else:
  print(Hmax + Wmax)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,M=map(int, input().split())
hl=np.array([0 for i in range(H+1)])
wl=np.array([0 for i in range(W+1)])
ms=[]
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.append([h,w])
a=max(hl)
b=max(wl)
hmax= [i for i, x in enumerate(hl) if x ==a]
wmax=[i for i, x in enumerate(wl) if x ==b]
# hmax=np.where(hl == hl.max())[0]
# wmax=np.where(wl == wl.max())[0]
a=max(hl)
b=max(wl)
bl=False
if len(hmax)*len(wmax)>M:
    bl=True
else:
    for x in hmax:
        for y in wmax:
            if [x,y] not in ms:
                bl=True
                break
        if bl:
            break
if bl:
    print(a+b)
else:
    print(a+b-1)

Submission status: Time Limit Exceeded

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

for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hw[(h0,w0)]+=1
    wd[w0]+=1

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')
for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break

print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)

Submission status: Time Limit Exceeded

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

# スペース区切りの整数の入力
h, w, m = map(int, input().split())

h_list = [0]*h
w_list = [0]*w

# print(h_list)
# print(w_list)

h_w_list = [[0 for j in range(w)] for i in range(h)]
# print(h_w_list)


for zzz in range(m):
  # print("---")
  bom_h, bom_w = map(int, input().split())
  # print(bom_h, bom_w)
  h_list[bom_h-1] = h_list[bom_h-1] + 1
  w_list[bom_w-1] = w_list[bom_w-1] + 1

  h_w_list[bom_h-1][bom_w-1] = "target"

  # print(h_list)
  # print(w_list)

# print(h_list)
# print(w_list)

h_max_indexs = [i for i, v in enumerate(h_list) if v == max(h_list)]
# print(h_max_indexs)

w_max_indexs = [i for i, v in enumerate(w_list) if v == max(w_list)]
# print(w_max_indexs)


double_chance = False
# print("---")
for h_index in h_max_indexs:
  for w_index in w_max_indexs:
    chance = h_w_list[h_index][w_index] != "target"

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_cand = [i+1 for i in range(len(h_lst)) if h_lst[i] == max(h_lst)]
w_cand = [i+1 for i in range(len(w_lst)) if w_lst[i] == max(w_lst)]
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
h,w,m = list(map(int,input().split()))

R = [0]*h
C = [0]*w
G = {}

for _ in range(m):
  a,b = list(map(int,input().split()))
  a,b = a-1, b-1
  R[a] += 1
  C[b] += 1
  G[(a,b)] = 1
  
best = 0
for i in range(h):
  for j in range(w):
    cor = 0
    if (i,j) in G:
      cor = 1
    best = max(best,R[i]+C[j] - cor)
    
print(best)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if not [cand_h[i], cand_w[j]] in object:
            ans = h_max + w_max
            break
            break
            
else:
   ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import heapq
from bisect import bisect_left,bisect

stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

H,W,M=nm()
r=[0]*(10**6)
c=[0]*(10**6)
ans=0
mass=[]
for i in range(M):
    h,w=nm()
    mass.append((h,w))
    r[h]+=1
    c[w]+=1

inds1=list(range(10**6))
inds1.sort(reverse=True,key=lambda x: r[x])

inds2=list(range(10**6))
inds2.sort(reverse=True,key=lambda x: c[x])

r.sort(reverse=True)
c.sort(reverse=True)

r1=0
l1=0

while(1):
    if(r[r1+1]==r[r1]):
        r1+=1
    else:
        break

while(1):
    if(c[l1+1]==c[l1]):
        l1+=1
    else:
        break



flag=False
for i in range(r1+1):
    for j in range(l1+1):
        flag=True
        for k in mass:
                if(k[0]==inds1[i] and k[1]==inds2[j]):
                    flag=False
        if(flag==True):
            print(r[0]+c[0])
            sys.exit(0)


print(r[0]+c[0]-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W,N = [int(i) for i in input().split()]
varriers = [[int(i)-1 for i in input().split()] for i in range(N)]
board = np.array([[0 for _ in range(W)] for i in range(H)], dtype=int)

for varrier in varriers:
    board[varrier[0], :] += 1
    board[:, varrier[1]] += 1
    board[varrier[0], varrier[1]] -= 1

print(board.max())

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    H, W, M = map(int, input().split())
    bombs = []
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append((h, w))
    bombs_set = set(bombs)
    g = list(zip(*bombs))
    g0 = collections.Counter(g[0])
    g1 = collections.Counter(g[1])
    g0items = list(g0.items()); g0items.sort(key=lambda x: x[1], reverse=True)
    g1items = list(g1.items()); g1items.sort(key=lambda x: x[1], reverse=True)
    x = g0items[0][0];countx = g0items[0][1]
    y = g1items[0][0];county = g1items[0][1]
    for xx, s in g0items:
        if s != countx:
            continue
        for yy, t in g1items:
            if t != county:
                continue
            if (xx, yy) not in bombs_set:
                x, y = xx, yy
                break
    ans = countx + county - ((x, y) in bombs)
    print(ans)


if __name__ == "__main__":
    main()

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 = map(int,input().split())
H = [0]*(h+1)
W = [0]*(w+1)
s = set([])
for i in range(m):
    a,b = map(int,input().split())
    s.add((a,b))

    H[a] += 1
    W[b] += 1

x = [0]*(h+1)
y = [0]*(w+1)
    
for i in range(h+1):
    x[i] = [i,H[i]]
for i in range(w+1):
    y[i] = [i,W[i]]

x.sort(key= lambda val : val[1],reverse=True)
y.sort(key= lambda val : val[1],reverse=True)

ma = x[0][1]
mb = y[0][1]

i,j = 0,0
sw = 0
while 1:
    if j > w:
        break
    if  x[i][1] == ma:
        if (x[i][0],y[j][0]) in s:
            pass
        else:
            if x[i][1]+y[j][1] == ma+mb:
                sw = 1
                break
        i += 1
    else:
        i = 0
        j += 1

    
print(ma+mb+sw-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hwlist = [list(map(int, input().split())) for i in range(M)]
a = []
b = []
for h in range(H):
  a.append(0)
for w in range(W):
  b.append(0)
for m in range(M):
    a[hwlist[m][0]-1] += 1
    b[hwlist[m][1]-1] += 1
max_a = max(a)
a_max_id = [i for i, v in enumerate(a) if v == max_a]
max_b = max(b)
b_max_id = [i for i, v in enumerate(b) if v == max_b]
for i in range(len(a_max_id)):
    for j in range(len(b_max_id)):
        if not [a_max_id[i]+1, b_max_id[j]+1] in hwlist:
            print(max_a + max_b)
            exit()
print(max_a + max_b - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8(i8,i8,i8[:,:],i8[:],i8[:],i8))
def sol(H,W,tar,row,col,res):
    for i in range(H):
        for j in range(W):
            res = max(res,row[i]+col[j]-tar[i,j])
    return res


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

    tar = np.array([[0 for j in range(W)] for i in range(H)])
    row = np.array([0 for i in range(H)])
    col = np.array([0 for j in range(W)])

    for i in range(M):
        h,w = map(int,input().split())
        tar[h-1,w-1] = 1
        row[h-1] += 1
        col[w-1] += 1

    res = sol(H,W,tar,row,col,0)

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
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
    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)
m_count=0
for k in P:
    if  k[0] in max_X and k [1] in max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    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())
P = [0]*(H+1)
Q = [0]*(W+1)
A = set()
for k in range(M):
  a,b = map(int,input().split())
  P[a] += 1
  Q[b] += 1
  A.add((a,b))
Pindex = [i for i, v in enumerate(P) if v == max(P)]
Qindex = [i for i, v in enumerate(Q) if v == max(Q)]
Pmax = P[Pindex[0]]
Qmax = Q[Qindex[0]]
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:
import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = []
for x in sys.stdin.readlines():
    H, W = map(int, x.split())
    bomb.append([H-1, W-1])
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)
for i in p:
    for j in q:
        if [i, j] not in bomb:
            print(ans + 1)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * M for i in range(2)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[0][i] = hi-1
    DST[1][i] = 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 = 0
for i in range(M):
    if (DST[0][i] in Hbomb) and (DST[1][i] 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:
H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
isExist = []
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    isExist.append((h,w))


HMinx = []
WMinx = []
Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax + Wmax

isExist = set(isExist)
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

cross = 0
not_cross = 0

for i in HMinx:
    for j in WMinx:
        if (i,j) in isExist:
            cross += 1
        else:
            not_cross += 1

if not_cross > 0:
    print(ans)
else:
    print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = (int(x) for x in input().split())

sumH = [0 for i in range(h)]
sumW = [0 for i in range(w)]
bomH = [0 for i in range(m)]
bomW = [0 for i in range(m)]

for i in range(m):
    hi,wi = (int(x) for x in input().split())
    sumH[ hi-1 ] += 1
    sumW[ wi-1 ] += 1
    bomH[ i ] = hi-1
    bomW[ i ] = wi-1

maxH = max(sumH)
maxW = max(sumW)
gHs = []
gWs = []
for i in range( h ):
    if maxH == sumH[i]:
        gHs.append(i)
for i in range( w ):
    if maxW == sumW[i]:
        gWs.append(i)

great = maxH + maxW
break_loop = False
for i in range( len(gHs) ):
    x = gHs[i]
    for j in range( len(gWs) ):
        y = gWs[j]
        flag = 0
        for k in range(m):
            if bomH[k] == x and bomW[k] == y:
                flag = 1
                break
        if flag == 0:
            break_loop = True
            break
    if break_loop:
        break

print( great - flag )

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(500005)
readline = sys.stdin.readline

def main():
    H, W, M = map(int, readline().rstrip().split())
    HW = [[False] * W for _ in range(H)]
    HB = [0] * H
    WB = [0] * W
    for _ in range(M):
        h, w = map(int, readline().rstrip().split())
        h -= 1
        w -= 1
        HW[h][w] = True
        HB[h] += 1
        WB[w] += 1
    hb = max(HB)
    max_h = [i for i, x in enumerate(HB) if x == hb]
    wb = max(WB)
    max_w = [i for i, x in enumerate(WB) if x == wb]
    
    ans = hb + wb
    for mh in max_h:
        for mw in max_w:
            if HW[mh][mw] == False:
                print(ans)
                sys.exit(0)
    print(ans - 1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

w_target = True # ターゲット入りのマスがあるかどうか
for r in range(h):
    if row[r] != rmax:
        continue
    for c in range(w):
        if col[c] != cmax:
            continue
        if [r, c] not in pos:
            w_target = False

if w_target:
    print(rmax + cmax - 1)
else:
    print(rmax + cmax)

Submission status: Time Limit Exceeded

Solution code:

h,w,m=map(int,input().split())
tate=[0]*(h+1)
yoko=[0]*(w+1)
box=[[] for i in range(h+1)]

for i in range(m):
    a, b = map(int, input().split())
    tate[a] += 1
    yoko[b] += 1
    box[a].append(b)
tmax = tate[0]
ymax = yoko[0]
tbox = []
ybox = []
for i in range(1,h+1):
    if tmax<tate[i]:
        tmax=tate[i]
        tbox=[i]
    elif tmax==tate[i]:
        tbox.append(i)
for i in range(1,w+1):
    if ymax<yoko[i]:
        ymax=yoko[i]
        ybox=[i]
    elif ymax==yoko[i]:
        ybox.append(i)
flag = True
for i in tbox:
    for j in ybox:
        if not(j in box[i]):
           flag = False
#print(tmax,ymax,tbox,ybox,flag,box)
if flag:
    print(tmax + ymax - 1)
else:
    print(tmax + ymax)

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w,m=map(int,input().split())
hw = []
H=[0 for _ in range(h)]
W=[0 for _ in range(w)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    hw.append((i,j))
    H[i-1] += 1
    W[j-1] += 1


hm = max(H)
wm = max(W)
hmi = [i for i, _ in enumerate(H) if _ == hm]
wmi = [i for i, _ in enumerate(W) if _ == wm]

c = 0
for h in hmi:
    for w in wmi:
        c += 1
        if not (h+1,w+1) in hw:
            print(hm+wm)
            sys.exit()
            
        if c>m:
            print(hm+wm-1)
            sys.exit()
else:
    print(hm+wm-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hli = [0]*h
wli = [0]*w
li = []
for i in range(m):
    a,b = map(int,input().split())
    li.append([a,b])
    hli[a-1] += 1
    wli[b-1] += 1
a = max(hli)
b = max(wli)
hli2 = []
wli2 = []
for i in range(h):
    if hli[i] == a:
        hli2.append(i+1)
for i in range(w):
    if wli[i] == b:
        wli2.append(i+1)
for i in hli2:
    for j in wli2:
        if [i,j] not in li:
            print(a + b)
            exit()
print(a + b - 1)