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())
pos = []
row = [0]*h
col = [0]*w
for i in range(m):
    r,c = map(int,input().split())
    pos.append([r,c])
    row[r-1] += 1
    col[c-1] += 1
targets = max(col)+max(row)

flag = 0
if max(row) > max(col):
    big = max(col)
    for i in range(len(col)):
        if col[i] == big:
            if [row.index(max(row))+1,i+1] not in pos:
                flag = 1
else:
    big = max(row)
    for i in range(len(row)):
        if row[i] == big:
            if [i+1,col.index(max(col))+1] not in pos:
                flag = 1
if flag == 0:
    targets -= 1
print(targets)

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)
for i, j in itertools.product(max_X, max_Y):
    if [i,j] in P:
        a=1
    else:
        a=0
        break
if a==0:
    answer=Max_X+Max_Y
else:
     answer=Max_X+Max_Y-1
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
H, W, M = list(map(int, input().split()))
row = np.zeros(H)
col = np.zeros(W)
#maps = np.zeros((H, W), dtype=np.int64)
maps = [[0] * W for i in range(H)]
for i in range(M):
    h, w =list(map(int, input().split()))
    row[h-1] += 1
    col[w-1] += 1
    maps[h-1][w-1] = 1

rowMax = row.max()
colMax = col.max()
rowMaxs = np.where(row == rowMax)
colMaxs = np.where(col == colMax)
d = 1
for i in rowMaxs[0]:
    for j in colMaxs[0]:
        if maps[i][j] == 0:
            d = 0
            break
    if d == 0:
        break

print(int(rowMax + colMax - d))

Submission status: Time Limit Exceeded

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

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

B = []
h = H
while h:
    h -= 1
    B.append([])
    
A = []
m = M
while m:
    m -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    B[x].append(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 j in B[i]:
            ans = True
            break
  
cnt = xm + ym         
print(cnt if ans else cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections

H,W,M = map(int, input().split())
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())
ch = collections.Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = collections.Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in zip(h,w):
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase


def main():
    h, w, m = map(int, input().split())
    row = [0] * h
    col = [0] * w
    d = set()
    ma = 0
    for i in range(m):
        x, y = map(int, input().split())
        row[x - 1] += 1
        col[y - 1] += 1
        d.add((x, y))
    for i in range(h):
        for j in range(w):
            ma = max(ma, col[j] + row[i] - (1 if (i + 1, j + 1) in d else 0))
    print(ma)
# region fastio
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter


def main():
    H, W, M = map(int, sys.stdin.readline().rstrip().split())
    Mh = [0] * H
    Mw = [0] * W
    B = []
    for i in range(M):
        h, w = map(int, sys.stdin.readline().rstrip().split())
        Mh[h - 1] += 1
        Mw[w - 1] += 1
        B.append((h - 1, w - 1))

    nh = max(Mh)
    nw = max(Mw)

    # 交差する場所に置かれた処理物があるか？
    lh = []
    lw = []
    while nh in Mh:
        ih = Mh.index(nh)
        lh.append(ih)
        Mh[ih] = 0
    while nw in Mw:
        iw = Mw.index(nw)
        lw.append(iw)
        Mw[iw] = 0

    for h in lh:
        for w in lw:
            if (h, w) not in B:
                print(nh + nw)
                return

    print(nh + nw - 1)


main()

Submission status: Time Limit Exceeded

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
h,w,m = inl()
H = [0] * h
W = [0] * w
hw = [[-1] for i in range(h)]
for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    H[a] += 1
    W[b] += 1
    hw[a].append(b)

hm = max(H)
wm = max(W)
hc = H.count(hm)
wc = W.count(wm)

ans = hm + wm

f = True
for i in range(hc):
    x = H.index(hm) + i
    d = W[::]
    for j in range(wc):
        y = d.index(wm) + j
        if not(y in hw[x]):
            f = False
            break
        d.pop(y - j)
    
    H.pop(x-i)

ans -= f
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

line = [int(i) for i in input().rstrip().split()]
H = line[0]
W = line[1]
M = line[2]

L = [[0]*W for i in range(H)]

#print(L)

for i in range(M):
  line = [int(i) for i in input().rstrip().split()]
  L[line[0]-1][line[1]-1] = 1
#print(L)
  
L = np.array(L)
P = np.count_nonzero(L == 1, axis = 1)
Q = np.count_nonzero(L == 1, axis = 0)
S = np.array([])
#print(P)
#print(Q)

for i in range(H):
  for j in range(W):
    if L[i][j] == 0:
      R = P[i]+Q[j]
      #print(R)
      S = np.append(S,R)
      
    else:
      R = P[i]+Q[j]-1
      #print(R)
      S = np.append(S,R)
#print(S)
print(int(np.max(S)))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = [int(m) for m in input().split(" ")]
bombByCol = {}
bombByRow = {}
A = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
  tmp = [int(a) for a in input().split(" ")]
  h = tmp[0] - 1
  w = tmp[1] - 1
  if str(w) in bombByCol:
    bombByCol[str(w)] += 1
  else:
    bombByCol[str(w)] = 1
  if str(h) in bombByRow:
    bombByRow[str(h)] += 1
  else:
    bombByRow[str(h)] = 1
  A[h][w] += 1

maxC = max(list(bombByCol.values()))
maxR = max(list(bombByRow.values()))
idxC = [int(k) for k, v in bombByCol.items() if v == maxC]
idxR = [int(k) for k, v in bombByRow.items() if v == maxR]

bombFlag = 1
for j in idxC:
  for k in idxR:
    if A[k][j] == 0:
      bombFlag = 0
      break
  if bombFlag == 0:
    break

print(maxC + maxR - bombFlag)

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)]
for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(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)):
        h_cand=[k for k, v in enumerate(h) if v == h_max[ii]+1]
        w_cand=[l for l, v in enumerate(w) if v == w_max[jj]+1]
        h_set = set(h_cand)
        w_set = set(w_cand)
        matched_list = list(h_set & w_set)
        #print(h_cand,w_cand)
        #print(matched_list)
        if len(matched_list)==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)

Submission status: Time Limit Exceeded

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

h,w,m=map(int,input().split())
l=[[0 for i in range(w+1)] for j in range(h+1)]
row=[0 for i in range(h+1)]
col=[0 for j in range(w+1)]

for i in range(m):
    x,y=map(int,input().split())
    l[x][y]=1
    row[x]+=1
    col[y]+=1
    
maxr=max(row)
maxc=max(col)
maxa=maxr+maxc
p=1
cl,rl=[],[]
for i in range(1,h+1):
    if(row[i]==maxr):rl.append(i)
for j in range(1,w+1):
    if(col[j]==maxc):cl.append(j)
    
for x in rl:
    for y in cl:
        if(l[x][y]==0):p=0;break
    
print(maxa-p)

Submission status: Time Limit Exceeded

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = [(0, 0) for _ in range(m)]
    row = [0] * h
    col = [0] * w
    for i in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target[i] = (hi, wi)
        row[hi] += 1
        col[wi] += 1
    r = max(row)
    ri = [i for i in range(h) if row[i] == r]
    c = 0
    for rii in ri:
        ci = col[:]
        for y, x in target:
            if y == rii:
                ci[x] -= 1
        c = max(max(ci), c)
    ans = r + c
    c = max(col)
    ci = [i for i in range(w) if col[i] == c]
    r = 0
    for cii in ci:
        ri = row[:]
        for y, x in target:
            if x == cii:
                ri[y] -= 1
        r = max(max(ri), r)
    ans = max(r + c, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w, m = map(int, input().split())

hcnt = [0] * w
wcnt = [0] * h
field = {}
for i in range(m):
    y, x = map(int, input().split())
    y -= 1; x -= 1
    wcnt[y] += 1
    hcnt[x] += 1
    row = field.get(y, {})
    row[x] = True
    field[y] = row
def f(y, x):
    return bool(field.get(y, {}).get(x))
# print(wcnt)
# print(hcnt)
hmax = max(hcnt)
wmax = max(wcnt)
ans = hmax + wmax - 1
for i in np.argsort(hcnt)[::-1]:
    if hcnt[i] != hmax:
        break
    for j in np.argsort(wcnt)[::-1]:
        if wcnt[j] != wmax:
            break
        if not f(j, i):
            print(ans + 1)
            __import__("sys").exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline
H, W, M = map(int, input().split())
Bn = [list(map(int, input().split())) for _ in range(M)]
Hn = [0 for _ in range(H)]
Wn = [0 for _ in range(W)]
B_d = {}
for B in Bn:
    BH, BW = B
    Hn[BH-1] += 1
    Wn[BW-1] += 1
    key = "{0}:{1}".format(BH, BW)
    B_d[key] = True
ans = 0
for i in range(H):
    for j in range(W):
        key2 = "{0}:{1}".format(i+1, j+1)
        if key2 in B_d:
            ans = max(ans, Hn[i]+Wn[j]-1)
        else:
            ans = max(ans, Hn[i]+Wn[j])
print(ans)

Submission status: Time Limit Exceeded

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

hdic = {}
wdic = {}
hws_h = {}

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

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

hs = []
ws = []

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

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

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

print(hmax + wmax - f)

Submission status: Time Limit Exceeded

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

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

H_list = [[0, i] for i in range(H + 1)] 
W_list = [[0, i] for i in range(W + 1)] 


S = set()
S_add = S.add
INF = 10 ** 6

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

ans = 0
H_list.sort(reverse=True)
W_list.sort(reverse=True)

tmp_H = H_list[0][0]
tmp_W = W_list[0][0]

for h in range(H):
    if H_list[h][0] + 2 < tmp_H:
        continue
    h_ = H_list[h][1]
    for w in range(W):
        if W_list[w][0] + 2 < tmp_W:
            break
        w_ = W_list[w][1]
        tmp = H_list[h][0] + W_list[w][0]
        if INF * h_ + w_ in S:
            tmp -= 1
        ans = max(ans, tmp)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import sys

h, w, m = map(int, input().split())
x = []
y = []
bomb = []
for i in range(m):
  tmp_x, tmp_y = map(int, input().split())
  x.append(tmp_x)
  y.append(tmp_y)
  bomb.append([tmp_x, tmp_y])

c_x = collections.Counter(x)
c_y = collections.Counter(y)
_max_x = c_x.most_common()[0][1]
_max_y = c_y.most_common()[0][1]
ys = c_y.most_common()
count = _max_x + _max_y - 1
      
tansaku_x = []
tansaku_y = []
for x, x_num in c_x.most_common():
  if x_num != _max_x:
    break
  tansaku_x.append(x)
for y, y_num in c_y.most_common():
  if y_num != _max_y:
    break
  tansaku_y.append(y)

for x in tansaku_x:
  for y in tansaku_y:
    if [x, y] not in bomb:
      print(count+1)
      sys.exit()
      
print(count)

Submission status: Time Limit Exceeded

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

counterH = Counter()
counterW = Counter()
targets = set()
for i in range(M):
    h,w = list(map(int,input().split()))
    counterH[h] += 1
    counterW[w] += 1
    targets.add((h,w))

max_w = 0
if M == 1:
    print(1)
else:
    ans = 2
    flg = False
    for count_H in counterH.most_common():
        for count_W in counterW.most_common():
            max_w = max(max_w,count_W[1])
            if max_w != count_W[1]:
                break
            # print(count_H,count_W)
            if (count_H[0],count_W[0]) in targets:
                ans = max(ans,count_H[1]+count_W[1]-1)
            else:
                ans = max(ans,count_H[1]+count_W[1])
                flg = True
            if flg:
                break
        if flg:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
import numpy as np

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

num = [[0]*w for i in range(h)]

for i in range(m):
    a,b = map(int,input().split())
    num[a-1][b-1] = 1

num = np.array(num)

Sumw = (np.sum(num , axis = 1))
point1  = np.argmax(Sumw)
Maxw = max(Sumw)

num = np.delete(num,point1,axis = 0)

Sumh = (np.sum(num , axis = 0))
Maxh = max(Sumh)

print(Maxw+Maxh)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    h, w, m = LI()
    mat = [[0 for i in range(w+1)] for i in range(h+1)]
    matt = [[0 for i in range(h+1)] for i in range(w+1)]
    boms = []
    for i in range(m):
        hi, wi = LI()
        mat[hi][wi] = 1
        matt[wi][hi] = 1
        boms.append((hi, wi))
    # matt = [list(x) for x in zip(*mat)]
    hsums = [sum(mat[i]) for i in range(1+h)]
    wsums = [sum(matt[i]) for i in range(1+w)]
    hsums_top = set()
    wsums_top = set()

    maxh = 0
    for i, top in enumerate(hsums):
        if maxh == top:
            hsums_top.add(i)
        elif maxh < top:
            maxh = top
            hsums_top = {i}

    maxw = 0
    for i, top in enumerate(wsums):
        if maxw == top:
            wsums_top.add(i)
        elif maxw < top:
            maxw = top
            wsums_top = {i}

    if len(hsums_top) * len(wsums_top) > m:
        print(maxh + maxw)
        return
    for i in hsums_top:
        for j in wsums_top:
            if mat[i][j] == 0:
                print(maxh + maxw)
                return
    print(maxh + maxw - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
xnum=[[0,i] for i in range(h)]
ynum=[[0,i] for i in range(w)]
hw=[]
xmax=[]
ymax=[]
for i in range(m):
  s,t=map(int,input().split())
  xnum[s-1][0]+=1
  ynum[t-1][0]+=1
  hw.append([s-1,t-1])
hw.sort()
xnum.sort()
ynum.sort()
xmax.append(xnum[-1][1])
ymax.append(ynum[-1][1])
for i in range(2,len(xnum)+1):
  if xnum[-1*i][0]==xnum[-1][0]:
    xmax.append(xnum[-1*i][1])
  else:
    break
for i in range(2,len(ynum)+1):
  if ynum[-1*i][0]==ynum[-1][0]:
    ymax.append(ynum[-1*i][1])
  else:
    break
flag=True
for i in xmax:
  for j in ymax:
    if [i,j] in hw:
      continue
    else:
      flag=False

if flag:
  ans=xnum[-1][0]+ynum[-1][0]-1
else:
  ans=xnum[-1][0]+ynum[-1][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int, input().split())
M=max(h, w)
lh=[0]*(M+1)
lw=[0]*(M+1)
point=[[-1,-1]]
for i in range(m):
  a,b=map(int, input().split())
  lh[a]=lh[a]+1
  lw[b]=lw[b]+1
  point.append([a,b])

mh=max(lh)
mw=max(lw)

pansh=[]
pansw=[]

pansh = [i for i, x in enumerate(lh) if x == mh]
pansw = [i for i, x in enumerate(lw) if x == mw]

d=0

for i in range(len(pansh)):
  for j in range(len(pansw)):
    if [pansh[i], pansw[j]] not in point:
      d=1

if d==0:
  print(mh+mw-1)
else:
  print(mh+mw)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

# 別変数の整数複数個
H, W, M = [int(x) for x in input().strip().split(" ")]

h_sums = np.zeros(H, int)
w_sums = np.zeros(W, int)
B = []
for _ in range(M):
    h, w = [int(x) for x in input().strip().split(" ")]
    h_sums[h-1] += 1
    w_sums[w-1] += 1
    B.append((h-1, w-1))

h_sum_max = max(h_sums)
w_sum_max = max(w_sums)

for h, hv in enumerate(h_sums):
    if hv != h_sum_max:
        continue
    for w, wv in enumerate(w_sums):
        if wv != w_sum_max:
            continue
        if (h, w) not in B:
            print(h_sum_max + w_sum_max)
            import sys; sys.exit(0)
print(h_sum_max + w_sum_max - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, M = [int(n) for n in input().split()]
row_sums = np.zeros(H)
col_sums = np.zeros(W)
coords = []
for i in range(M):
    h, w = [int(n) for n in input().split()]
    row_sums[h-1] += 1
    col_sums[w-1] += 1
    coords.append((h, w))

col_indexes = np.argwhere(col_sums==col_sums.max()).flatten().tolist()
row_indexes = np.argwhere(row_sums==row_sums.max()).flatten().tolist()

# print('coords:', coords)
# print('col indexes:', col_indexes)
# print('row_indexes:', row_indexes)
# print('col_sums:', col_sums)
# print('row_sums:', row_sums)

intersection_without_bomb = False
for row_idx in row_indexes:
    for col_idx in col_indexes:
        if (row_idx+1, col_idx+1) not in coords:
            # print('ri, ci : ', row_idx, col_idx)
            intersection_without_bomb = True
            break
    if intersection_without_bomb:
        break

if intersection_without_bomb:
    print(int(col_sums.max() + row_sums.max()))
else:
    print(int(col_sums.max() + row_sums.max()) - 1)

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)]
    ay = [0]*h
    ax = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1
        c[x[0]][x[1]] = 1

    my = max(ay)
    mx = max(ax)
    by = [i for i, x in enumerate(ay) if x == my]
    bx = [i for i, x in enumerate(ax) if x == mx]

    ans = my + mx
    tmp = 1
    for y in by:
        for x in bx:
            if c[y][x] == 0:
               tmp = 0
               break
    print(ans - tmp)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w,m = map(int,input().split())
H = [0]*(h)
W = [0]*(w)
ch = [[False]*w for _ in range(h)]
for _ in range(m):
    a,b = map(int,input().split())
    H[a-1] += 1
    W[b-1] += 1
    ch[a-1][b-1] = True
hm = max(H)
wm = max(W)
for i in range(len(H)):
    if H[i] != hm:
        continue
    for j in range(len(W)):
        if W[j] != wm:
            continue
        if ch[i][j] != True:
            print(hm+wm)
            sys.exit()
print(hm+wm-1)

Submission status: Time Limit Exceeded

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

h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = map(int, input().split())


S = Counter(h)
T = Counter(w)

if (S.most_common()[0][1] > T.most_common()[0][1]):
    for i in range(M):
        if (h[i] == S.most_common()[0][0]):
            w[i] = 'boom'

    w1 = [s for s in w if s != 'boom']
    T = Counter(w1)
    for i in range(len(w1)):
        if (w1[i] == T.most_common()[0][0]):
            w1[i] = 'boom' 

    w2 = [s for s in w1 if s != 'boom']
    print(M-len(w2))

else:
    for i in range(M):
        if (w[i] == T.most_common()[0][0]):
            h[i] = 'boom'

    h1 = [s for s in h if s != 'boom']
    S = Counter(h1)
    for i in range(len(h1)):
        if (h1[i] == S.most_common()[0][0]):
            h1[i] = 'boom' 

    h2 = [s for s in h1 if s != 'boom']
    print(M-len(h2))

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())
#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(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=[i for i, x in enumerate(hb) if x == max(hb)]
wmx=[i for i, x in enumerate(wb) if x == max(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:
h, w, m = map(int, input().split())
bomb = []
H = []
W = []
dH = {}
dW = {}
for i in range(m):
    a, b = map(int, input().split())
    H.append(a)
    if a in dH:
        dH[a] += 1
    else:
        dH[a] = 1
    W.append(b)
    if b in dW:
        dW[b] += 1
    else:
        dW[b] = 1
    bomb.append((a, b))
maxH = max(dH.values())
maxH_list = []
for i in dH:
    if dH[i] == maxH:
        maxH_list.append(i)
maxW = max(dW.values())
maxW_list = []
for i in dW:
    if dW[i] == maxW:
        maxW_list.append(i)
for i in maxH_list:
    for j in maxW_list:
        if (i, j) not in bomb:
            print(dH[i] + dW[j])
            break
    else:
        continue
    break
else:
    print(dH[maxH_list[0]] + dW[maxW_list[0]] - 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= [i for i, x in enumerate(hl) if x ==a]
wmax=[i for i, x in enumerate(wl) if x ==b]
a=max(hl)
b=max(wl)
bl=False
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:
from collections import defaultdict
H, W, M = map(int, input().split())
tate = defaultdict(int)
yoko = defaultdict(int)
T = {}
for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1]+= 1
    T[(h-1, w-1)] = 1

tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_m = tate[0][1]
yoko_m = yoko[0][1]
ans = 0
for i in range(len(tate)):
    if tate[i][1] == tate_m:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 1)
                else:
                    ans = max(ans, tate_m + yoko_m)
            else:
                break
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

H, W, M = map(int, input().split())
h_count = [[i, 0] for i in range(H)]
w_count = [[i, 0] for i in range(W)]
exist = dict()
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    h_count[h][1] += 1
    w_count[w][1] += 1
    exist[(h, w)] = 1

h_count.sort(key=itemgetter(1), reverse=True)
w_count.sort(key=itemgetter(1), reverse=True)
h_max = h_count[0][1]
w_max = w_count[0][1]
res = 0
for h in h_count:
    if h[1] != h_max:
        break
    for w in w_count:
        if w[1] != w_max:
            break
        val = h[1] + w[1]
        if exist.get((h[0], w[0]), 0):
            val -= 1
        res = max(res, val)
print(res)

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
    hwset = [set() for _ in range(H)]

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hwset[h-1].add(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)]

    flag = False
    for h in hmax:
        for w in wmax:
            if w+1 not in hwset[h]:
                flag = True
                break

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





if __name__ == '__main__':
    solve()