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
readline=sys.stdin.readline

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

hcol = [[0,i] for i in range(H)]
wcol = [[0,i] for i in range(W)]

P = set()
for i in range(M):
  h,w = map(int,readline().split())
  h -= 1
  w -= 1
  hcol[h][0] += 1
  wcol[w][0] += 1
  P.add((h,w))
  
hcol = sorted(hcol, key = lambda x:x[0], reverse = True)
wcol = sorted(wcol, key = lambda x:x[0], reverse = True)

hmax = hcol[0][0]
wmax = wcol[0][0]

ans = 0
hind = 0
wind = 0
while hind < H:
  while wind < W:
    val = hcol[hind][0] + wcol[wind][0]
    if (hcol[hind][1],wcol[wind][1]) in P:
      val -= 1
    if ans < val:
      ans = val
    wind += 1
    if wind == W or wcol[wind][0] < wmax:
      wind = 0
      break
  hind += 1
  if hind == H or hcol[hind][0] < hmax:
    break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bo=[[0 for i in range(w)]for i in range(h)]
tate=[0 for i in range(h)]
yoko=[0 for i in range(w)]
for i in range(m):
    a,b=map(int,input().split())
    bo[a-1][b-1]=1
    tate[a-1]+=1
    yoko[b-1]+=1
tatem=max(tate)
yokom=max(yoko)
tate1=[]
yoko1=[]
for i in range(len(tate)):
    if tate[i]==tatem:
        tate1.append(i)
for i in range(len(yoko)):
    if yoko[i]==yokom:
        yoko1.append(i)

if tatem+yokom==h+w:
    print(h+w-1)
else:
    for i in range(len(tate1)):
        for j in range(len(yoko1)):
            if bo[tate1[i]][yoko1[j]]==0:
                print(tatem+yokom)
                break
        else:
            continue
        break
    else:
        print(tatem+yokom-1)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H ={i:0 for i in range(1,H+1)}
bom_W ={i:0 for i in range(1,W+1)}
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]


ans =0
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==1:
            ans =max(ans,v_h +v_w -1)
        else:
            ans =max(ans,v_h +v_w )
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import itertools

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

    listH=[]
    listW=[]
    for i in range(M):
        h,w=map(int,input().split())
        listH.append(h)
        listW.append(w)

    countedh=collections.Counter(listH)
    countedw=collections.Counter(listW)

    retH = [letter for letter,count in countedh.most_common() if count == countedh.most_common()[0][1]]
    retW = [letter for letter,count in countedw.most_common() if count == countedw.most_common()[0][1]]

    # print(retH)
    # print(retW)
    tmp=0
    tmpMax=0

    for i in range(len(retH)):
        for j in range(len(retW)):
            tmp=0
            for k in range(M):
                if(listH[k]==retH[i] or listW[k]==retW[j]):
                    tmp+=1
            if(tmp>tmpMax):
                tmpMax=tmp
    
    print(tmpMax)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from collections import Counter
import time
import datetime
from math import sqrt,gcd

# def time_t():
#     print("Current date and time: " , datetime.datetime.now())
#     print("Current year: ", datetime.date.today().strftime("%Y"))
#     print("Month of year: ", datetime.date.today().strftime("%B"))
#     print("Week number of the year: ", datetime.date.today().strftime("%W"))
#     print("Weekday of the week: ", datetime.date.today().strftime("%w"))
#     print("Day of year: ", datetime.date.today().strftime("%j"))
#     print("Day of the month : ", datetime.date.today().strftime("%d"))
#     print("Day of week: ", datetime.date.today().strftime("%A"))

def ip(): return int(sys.stdin.readline())

def sip(): return sys.stdin.readline()

def mip(): return map(int,sys.stdin.readline().split())

def mips(): return map(str,sys.stdin.readline().split())

def lip(): return list(map(int,sys.stdin.readline().split()))

def matip(n,m):
    lst=[]
    for i in range(n):
        arr = lip()
        lst.append(arr)
    return lst

def factors(n): # find the factors of a number
    return list(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

def minJumps(arr, n): #to reach from 0 to n-1 in the array in minimum steps
    jumps = [0 for i in range(n)]
    if (n == 0) or (arr[0] == 0):
        return float('inf')
    jumps[0] = 0
    for i in range(1, n):
        jumps[i] = float('inf')
        for j in range(i):
            if (i <= j + arr[j]) and (jumps[j] != float('inf')):
                jumps[i] = min(jumps[i], jumps[j] + 1)
                break
    return jumps[n-1]

def dic(arr): # converting list into dict of count
    return Counter(arr)

def check_prime(n):
    if n<2:
        return False
    for i in range(2,int(n**(0.5))+1,2):
        if n%i==0:
            return False
    return True 

# --------------------------------------------------------- #
# sys.stdin = open('input.txt','r')
# sys.stdout = open('output.txt','w')
# --------------------------------------------------------- #

h,w,m = mip()
x = {}
y = {}
final = []
while m:
    m-=1
    l,p = mip()
    final.append([l,p])
    if l not in x:
        x[l] = 1
    else:
        x[l]+=1
    if p not in y:
        y[p] = 1
    else:
        y[p] +=1
v = list(x.values()) 
x_val = max(v)
lst = []
arr = []
for item in x:
    if x[item]==x_val:
        lst.append(item)
v = list(y.values())
y_val = max(v)
for item in y:
    if y[item]==y_val:
        arr.append(item)
flag = 0
for item in lst:
    for kachoda in arr:
        if [item,kachoda] not in final:
            flag = 1
            break
if flag==1:
    print(x_val+y_val)
else:
    print(x_val+y_val-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hs = [0] * h
ws = [0] * w
pos = []
for _ in range(m):
    hi, wi = map(int, input().split())
    pos.append([hi, wi])
    hs[hi-1] += 1
    ws[wi-1] += 1
    
mh = max(hs)
mhs = []
for i in range(h):
    if hs[i] == mh:
        mhs.append(i+1)

mw = max(ws)
mws = []
for i in range(w):
    if ws[i] == mw:
        mws.append(i+1)

flg = False
for i in mhs:
    for j in mws:
        if [i, j] not in pos:
            flg = True
            print(mh + mw)
            break
    if flg:
        break
else:
    print(mh + mw - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    H, W, M = map(int, input().split())
    d = defaultdict(int)
    e = defaultdict(int)
    X = []
    for _ in range(M):
        h, w = map(int, input().split())
        d[h] += 1
        e[w] += 1
        X.append((h,w))
    
    a = max(d.values())
    b = max(e.values())
    cand_d = []
    cand_e = []
    for i, j in d.items():
        if j == a:
            cand_d.append(i)

    for i, j in e.items():
        if j == b:
            cand_e.append(i)

    for i in cand_d:
        for j in cand_e:
            if not (i,j) in X:
                ans = a + b
                print(ans)
                exit()

    print(a + b - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input =sys.stdin.readline
from collections import Counter

H,W,M = (int(x) for x in input().rstrip('\n').split())
ds = []
for _ in range(M):
  h,w = (int(x) for x in input().rstrip('\n').split())
  ds.append([h,w])
hs = [x[0] for x in ds]
ws = [x[1] for x in ds]
hs2 = Counter(hs)
ws2 = Counter(ws)
max_h=hs2.most_common()[0][1]
max_w=ws2.most_common()[0][1]
mh = [k for k,v in hs2.items() if v==max_h]
mw = [k for k,v in ws2.items() if v==max_w]
if any([x,y] not in ds for x in mh for y in mw):
  print(max_h+max_w)
else:
  print(max_h+max_w-1)

Submission status: Time Limit Exceeded

Solution code:
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 in l_h_2:
    flag = False
    for j in l_w_2:
        if j not in l_hw[i]:
            flag = True
            break
    if flag:
        break
else:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
l=[0]*n
d=[0]*m
p=[]
for i in range(n):
    t=[]
    for j in range(m):
        t.append(0)
    p.append(t)
for u in range(k):
    x,y=map(int,input().split())
    l[x-1]+=1
    d[y-1]+=1
    p[x-1][y-1]=1
x=max(l)
y=max(d)
w=0
for i in range(n):
    for j in range(m):
        s=l[i]+d[j]
        if(p[i][j]==1):
            s-=1
        w=max(w,s)
print(w)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

H,W,M = list(map(int,input().split()))
data_list = [list(map(int,input().split(" "))) for i in range(M)]

cnt = 0
Max = 0

H_rec = 0
W_rec = 0

for hei in range(1,H+1):
    for wei in range(1,W+1):
        for X in data_list:
            if hei == X[0] or wei == X[1]:
                cnt += 1

        if Max < cnt:
            Max = cnt
            H_rec = hei
            W_rec = wei

        cnt = 0

print(Max)

Submission status: Time Limit Exceeded

Solution code:
def mis():
    return map(int, input().split())

def main():
    H, W, M = mis()
    B = set()
    BH = [0]*H
    BW = [0]*W
    for _ in range(M):
        h, w = mis()
        h -= 1
        w -= 1
        BH[h] += 1
        BW[w] += 1
        B.add((h, w))
    #
    maxbh = max(BH)
    maxbw = max(BW)
    for h in range(H):
        if BH[h]==maxbh:
            for w in range(W):
                if BW[w]==maxbw:
                    if (h, w) not in B:
                        print(maxbh + maxbw)
                        return
    print(maxbh + maxbw - 1)

main()

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.items(), key=lambda x: x[1])

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = []
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.append([x, y])
  
a = []
b = []
c = max(h)
d = max(w)
for i in range(H+1):
  if h[i] == c:
    a.append(i)
for i in range(W+1):
  if w[i] == d:
    b.append(i)

flag = False
for s in a:
  for t in b:
    if [s, t] not in l:
      flag = True
      break
if flag:
  ans = c+d
else:
  ans = c+d-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = []
for i in range(M):
    h, w = map(int, input().split())
    t.append((h-1, w-1))
    h_t[h-1]+=1
    w_t[w-1]+=1
h_max = max(h_t)
h_max_list = [i for i, v in enumerate(h_t) if v == h_max]
w_max = max(w_t)
w_max_list = [i for i, v in enumerate(w_t) if v == w_max]

for h in h_max_list:
    for w in w_max_list:
        if (h, w) not in t:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))


H,W,M=map(int, input().split())
#P = [list(map(int,input().split())) for i in range(M)]
Hlist=[0] * M
Wlist=[0] * M
P = []
for i in range(M):
    Hlist[i],Wlist[i]=map(int, input().split())
    P.append([Hlist[i],Wlist[i]])


HC = Counter(Hlist)
HD = HC.most_common()
WC = Counter(Wlist)
WD = WC.most_common()

Hmax = HD[0][1]
Wmax = WD[0][1]
ans = Hmax + Wmax


for i in range(len(HD)):
    if HD[i][1] != Hmax:
        break
    for j in range(len(WD)):
        if WD[j][1] != Wmax:
            break
        tmp = [HD[i][0],WD[j][0]]
        if (tmp in P) == False:
            print(ans)
            sys.exit()
        

print(ans-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


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

h,w,m=map(int,input().split())
#inp=[(random.randrange(1,h+1),random.randrange(1,w+1)) for i in range(m)]
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb.append([hh,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 [i,j] in bmb:
      print(mhb+mwb)
      fl=True
      break
  if fl:
    break
else:
  print(mhb+mwb-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H,W,M = map(int,input().split())
lsx = [0] + [0]*H
lsy = [0] + [0]*W
lsxy = []
for i in range(M):
    x,y = map(int,input().split())
    lsx[x] += 1
    lsy[y] += 1
    lsxy.append((x,y))
maxx = max(lsx)
maxy = max(lsy)
lsmaxx = [i for i, x in enumerate(lsx) if x == maxx]
lsmaxy = [i for i, x in enumerate(lsy) if x == maxy]
lsp = list(itertools.product(lsmaxx,lsmaxy))
ii = 0
for i in range(M):
    if lsxy[i] in lsp:
        ii += 1
if len(lsp)-ii == 0:
    factor = 1
else:
    factor = 0
print(maxx+maxy-factor)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    for ws in dicwi:
        if ws[1] != wmax:
            break
        if ws[0] not in havew[hs[0]]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

Submission status: Time Limit Exceeded

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

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

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

h_max = 0
w_max = 0

h_maxlist = []
w_maxlist = []

ans = 0
ans_tmp = 0

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

    h_count[h_in] += 1
    if h_count[h_in] > h_max:
        h_max = h_count[h_in]
        h_maxlist = [h_in]
    elif h_count[h_in] == h_max:
        h_maxlist.append(h_in)

    w_count[w_in] += 1
    if w_count[w_in] > w_max:
        w_max = w_count[w_in]
        w_maxlist = [w_in]
    elif w_count[w_in] == w_max:
        w_maxlist.append(w_in)


for i in range(len(h_maxlist)):
    tar_h = h_maxlist[i]
    for j in range(len(w_maxlist)):
        tar_w = w_maxlist[j]
        if (tar_h, tar_w) in tar_list:
            ans_tmp = h_count[tar_h] + w_count[tar_w] - 1
            ans = max(ans, ans_tmp)
        else:
            ans_tmp = h_count[tar_h] + w_count[tar_w]
            ans = max(ans, ans_tmp)


print("{}".format(ans))

Submission status: Time Limit Exceeded

Solution code:

from itertools import product

H, W, M = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(M)]

B = []
Bh = [0] * H
Bw = [0] * W
for h, w in X:
	B.append((h-1, w-1))
	Bh[h-1] += 1
	Bw[w-1] += 1

n = 0
for h, w in product(range(H), range(W)):
	tmp = Bh[h] + Bw[w]
	if (h, w) in B:
		tmp -= 1
	n = max(n, tmp)

print(n)

Submission status: Time Limit Exceeded

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

X = [0] * H
Y = [0] * W

A = []
while M:
    M -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    X[x] += 1
    Y[y] += 1

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = False
for i in xms:
    for j in yms:
        if not (i, j) in A:
            ans = True
  
cnt = xm + ym         
print(cnt if ans else cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    x = set()

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

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

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

    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:
def main():
    import collections

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

    zahyou = [[0 for i in range(W)] for j in range(H)]
    zahyou_H = [0 for i in range(H)]
    zahyou_W = [0 for i in range(W)]

    for i in range(M_ko):
        height, width = map(int, input().split())

        zahyou[height - 1][width - 1] = 1
        
        zahyou_H[height - 1] += 1
        zahyou_W[width - 1] += 1

    CTR_H = collections.Counter(zahyou_H)
    CTR_W = collections.Counter(zahyou_W)

    max_h = max(zahyou_H)
    max_w = max(zahyou_W)

    len_h = CTR_H[max_h]
    len_w = CTR_W[max_w]

    index_h = [i for i, x in enumerate(zahyou_H) if x == max_h]
    index_w = [i for i, x in enumerate(zahyou_W) if x == max_w]


    maxi = max_h + max_w
    FLAG = False


    if (len_h == 1 and len_w == 1):    
        maxi -= zahyou[index_h[0]][index_w[0]]


    else:
        for i in range(len_h):        
            for j in range(len_w):
                val = zahyou[index_h[i]][index_w[j]]
                
                if (val == 0):
                    FLAG = True
                    break
        
        if (not FLAG):
            maxi -= 1

    print(maxi)
    # print(zahyou_H, zahyou_W)
    # print(index_h,index_w)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    h, w, m = map(int, input().split())
    rows = [0] * h
    cols = [0] * w
    bombs = set()
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        bombs.add((a-1, b-1))
    rm = max(rows)
    cm = max(cols)
    rs = [i for i, v in enumerate(rows) if v == rm]
    cs = [i for i, v in enumerate(cols) if v == cm]
    r = rm + cm
    p = []
    for rse in rs:
        for cse in cs:
            if (rse, cse) in bombs:
                p.append(1)
            else:
                p.append(0)
    r -= min(p)
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, m = ns()

    hm = [0 for _ in range(h)]
    wm = [0 for _ in range(w)]

    m_pos = {}

    for _ in range(m):
        hi, wi = ns()
        hi, wi = hi - 1, wi - 1
        hm[hi] += 1
        wm[wi] += 1

        if hi in m_pos.keys():
            m_pos[hi].add(wi)
        else:
            m_pos[hi] = {wi}

    h_max = []
    w_max = []

    tmax = -1
    for i, hi in enumerate(hm):
        if hi > tmax:
            tmax = hi
            h_max = [i]
        elif hi == tmax:
            h_max.append(i)

    tmax = -1
    for i, wi in enumerate(wm):
        if wi > tmax:
            tmax = wi
            w_max = [i]
        elif wi == tmax:
            w_max.append(i)

    ans = 0

    for hi in h_max:
        for wi in w_max:
            if wi in m_pos[hi]:
                ans = max(ans, hm[hi] + wm[wi] - 1)

            else:
                ans = max(ans, hm[hi] + wm[wi])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
S = [[0 for _ in range(w)] for _ in range(h)]
count_h = [0 for _ in range(h)]
count_w = [0 for _ in range(w)]
for _ in range(m):
    i,j = map(int,input().split());i-=1;j-=1
    S[i][j] = 1
    count_h[i]+=1; count_w[j] +=1
max_h = max(count_h);max_w = max(count_w)
ind_h = []
for i in range(h):
    if count_h[i] == max_h:
        ind_h.append(i)
        
ind_w = []
for j in range(w):
    if count_w[j] == max_w:
        ind_w.append(j)

flag = 0
for i in ind_h:
    flag2 = 0
    for j in ind_w:
        if S[i][j]==0:
            flag = 1
            flag2=1
            break
    if flag2==1:
        break
            
if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w-1)

Submission status: Time Limit Exceeded

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

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

xcmax = max( xcnt.values() )
ycmax = max( ycnt.values() )
xlist = [k for k,v in xcnt.items() if v == xcmax]
ylist = [k for k,v in ycnt.items() if v == ycmax]
rest = [i for i in t if (i[0] in xlist) and (i[1] in ylist)]

if len( rest ) == len(xlist) * len(ylist):
  print( xcmax + ycmax -1 )
else:
  print( xcmax + ycmax )

Submission status: Time Limit Exceeded

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

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

H_list = [0] * (H + 1)
W_list = [0] * (W + 1)


S = set()
INF = 10 ** 6

for _ in range(M):
    a, b = map(int, input().split())
    tmp = INF * a + b
    S.add(tmp)
    H_list[a] += 1
    W_list[b] += 1

ans = 0
for h in range(1, H + 1):
    for w in range(1, W + 1):
        tmp = H_list[h] + W_list[w]
        if INF * h + w in S:
            tmp -= 1
        ans = max(ans, tmp)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
hh, ww, m = map(int, input().split())

ll = []
hl = [0 for _ in range(hh)]
wl = [0 for _ in range(ww)]

for i in range(m):
  h, w = map(int, input().split())
  ll.append([h,w])
  hl[h-1] += 1
  wl[w-1] += 1  

h_max = max(hl)
w_max = max(wl)

h_inx = []
w_inx = []

for i in range(hh):
  if hl[i] == h_max:
    h_inx.append(i)
  else:
    pass
for j in range(ww):
  if wl[j] == w_max:
    w_inx.append(j)
  else:
    pass

for hi in h_inx:
  for wi in w_inx:
    if [hi+1, wi+1] not in ll:
      print(h_max + w_max)
      exit()
    else:
      pass

print(h_max + w_max -1)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H ={i:0 for i in range(1,H+1)}
bom_W ={i:0 for i in range(1,W+1)}
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]


ans =0
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==1:
            ans =max(ans,v_h +v_w -1)
        else:
            ans =max(ans,v_h +v_w )
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = deque([b])
  else:
    dic[a].append(b)

  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)

  #ans[a][b]+=1

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

print(mh+mw-1)

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
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hwmatrix = [[0 for _ in range(W)] for _ in range(H)]

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

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

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

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





if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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


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

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