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())
HW=[list(map(int,input().split())) for _ in range(m)]

DP=[[[0,0] for _ in range(w)] for _ in range(h)]
MAP=[["." for _ in range(w)] for _ in range(h)]
for H,W in HW:
    DP[H-1][W-1]=[1,1]
    MAP[H-1][W-1]="#"

for i in range(h):
    for j in range(1,w):
        DP[i][j][0] +=DP[i][j-1][0]

for i in range(w):
    for j in range(1,h):
        DP[j][i][1] +=DP[j-1][i][1]

cnt=0
for i in range(h):
    for j in range(w):
        num=DP[i][w-1][0]+DP[h-1][j][1]
        if MAP[i][j]=="#":num -=1
        cnt=max(cnt,num)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from random import randint
from collections import defaultdict
from numba import njit
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            a -= (ypsi,xpsi) in s
            ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    # M[i] = [mh, mw]
    count_row[mh-1] += 1
    count_col[mw-1] += 1
max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
ans = max(count_row) + max(count_col) -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
X = [[0 for i in range(w)] for _ in range(h)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
for i in range(m):
    mh, mw = list(map(int, input().split()))
    X[mh-1][mw-1] = 1
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if X[i][j] == 0:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(m):
    hb[hw[i][0]-1] += 1
    wb[hw[i][1]-1] += 1
    M[hw[i][0]-1][hw[i][1]-1] = -1

max_h = max(hb)
max_w = max(wb)
ans = max_h + max_w
count = hb.count(max_h) * wb.count(max_w)
for i in range(m):
    if hb[hw[i][0]-1] == max_h and wb[hw[i][1]-1] == max_w:
        count -= 1
if count <= 0:
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
spot = []
tate = [0 for i in range(h)]
yoko = [0 for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  spot.append([x, y])
  tate[x-1] += 1
  yoko[y-1] += 1
mt = max(tate)
my = max(yoko)
maxh = []
maxw = []
for i in range(h):
  if(tate[i] == mt):
    maxh.append(i)
for i in range(w):
  if(yoko[i] == my):
    maxw.append(i)
maxb = 0
frag = False
for i in range(len(maxh)):
  for j in range(len(maxw)):
    if(not([maxh[i]+1, maxw[j]+1] in spot)):
      frag = True
if(frag):
  print(mt+my)
else:
  print(mt+my-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bH = [0 for _ in range(H)]
bW = [0 for _ in range(W)]
bom = []
for _ in range(M):
  h, w = map(int, input().split())
  bom.append([h, w])
  bH[h-1] = bH[h-1] + 1
  bW[w-1] = bW[w-1] + 1
mH = max(bH)
mW = max(bW)
mHl = []
mWl = []
for i in range(len(bH)):
  if bH[i] == mH:
    mHl.append(i+1)
for i in range(len(bW)):
  if bW[i] == mW:
    mWl.append(i+1)
f = False
for h in mHl:
  for w in mWl:
    if not [h, w] in bom:
      print(mH + mW)
      f = True
      break
  if f:
    break
if not f:
  print(mH + mW - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
row = [0]*H
column = [0]*W
bomb = []

for _ in range(M):
  h, w = map(int, input().split())
  row[h-1] += 1
  column[w-1] += 1
  bomb.append((h-1, w-1))
max_row = max(row)
max_column = max(column)
max_row_index = [i for i, x in enumerate(row) if x == max_row]
max_column_index = [i for i, x in enumerate(column) if x == max_column]

from itertools import product
max_comb = list(product(max_row_index, max_column_index))

for x in bomb:
  if x in max_comb:
    max_comb.remove(x)
if max_comb:
  print(max_row+max_column)
else:
  print(max_row+max_column-1)

Submission status: Time Limit Exceeded

Solution code:
# E
from collections import Counter

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

most_h,most_w=Counter(h).most_common(),Counter(w).most_common()

def max_values(lis):
    max_num=lis[0][1]
    for i in range(len(lis)):
        if lis[i][1]<max_num:
            res=lis[:i]
            break
    else:
        res=lis
    return res

most_h=max_values(most_h)
most_w=max_values(most_w)

res=-1
k=0
for i,i_n in most_h:
    for j,j_n in most_w:
        if not (i,j) in bomb or k>M:
            res=i_n+j_n
            break
        k+=1
    if res>-1:
        break
else:
    res=i_n+j_n-1
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
row = [0]*H
column = [0]*W
bomb = []

for _ in range(M):
  h, w = map(int, input().split())
  row[h-1] += 1
  column[w-1] += 1
  bomb.append((h-1, w-1))
max_row = max(row)
max_column = max(column)
max_row_index = [i for i, x in enumerate(row) if x == max_row]
max_column_index = [i for i, x in enumerate(column) if x == max_column]

ans = 0
for i in max_row_index:
  for j in max_column_index:
    if (i, j) not in bomb:
      ans = max_row + max_column
      break
if ans:
  print(ans)
else:
  print(max_row + max_column - 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w, m = map(int, input().split())
    hp = [0]*h
    wp = [0]*w
    hw = []
    for _ in range(m):
        h1, w1 = map(int, input().split())
        hp[h1-1] += 1
        wp[w1-1] += 1
        hw.append([h1, w1])

    h_max = max(hp)
    w_max = max(wp)

    hh = [i+1 for i, v in enumerate(hp) if v == h_max]
    ww = [i+1 for i, v in enumerate(wp) if v == w_max]


    ans = h_max + w_max
    for hb in hh:
        for wb in ww:
            if [hb, wb] not in hw:
                print(ans)
                exit()
    print(ans-1)


if __name__== '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# E
from collections import Counter

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

most_h,most_w=Counter(h).most_common(),Counter(w).most_common()

def max_values(lis):
    max_num=lis[0][1]
    for i in range(len(lis)):
        if lis[i][1]<max_num:
            res=lis[:i]
            break
    else:
        res=lis
    return res

most_h=max_values(most_h)
most_w=max_values(most_w)

res=-1
for i,i_n in most_h:
    for j,j_n in most_w:
        if not (i,j) in bomb:
            res=i_n+j_n
            break
    if res>-1:
        break
else:
    res=i_n+j_n-1
print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hp = [0]*h
wp = [0]*w
hw = []
for _ in range(m):
    h1, w1 = map(int, input().split())
    hp[h1-1] += 1
    wp[w1-1] += 1
    hw.append([h1, w1])

h_max = max(hp)
w_max = max(wp)

hh = [i+1 for i, v in enumerate(hp) if v == h_max]
ww = [i+1 for i, v in enumerate(wp) if v == w_max]


ans = h_max + w_max
for hb in hh:
    for wb in ww:
        if [hb, wb] not in hw:
            print(ans)
            exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
def find():
    h,w,m=map(int,input().split())
    idx=[]

    for i in range(m):
      var=list(map(int,input().split()))
      idx.append(var)


    r={}
    c={}
    maze=[[0 for j in range(w)]for i in range(h)]

    for i in idx:
      maze[i[0]-1][i[1]-1]=1
      r.setdefault(i[0]-1,0)
      r[i[0]-1]+=1
      c.setdefault(i[1]-1,0)
      c[i[1]-1]+=1

    ans=0
    maxval=0



    row=[]
    col=[]
    maxr=max(r.values())
    maxc=max(c.values())
    for i in range(h):
      r.setdefault(i,0)
      if r[i]==maxr:
        row.append(i)
      

    for j in range(w):
      c.setdefault(j,0)
      if c[j]==maxc:
        col.append(j)
    
    for i in row:
      for j in col:
        if(maze[i][j]==0):
          return maxc+maxr
         
        
    return maxc+maxr-1
 
print(find())

Submission status: Time Limit Exceeded

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

h_dict = [0]+[set() for i in range(H)]
w_dict = [0]+[set() for i in range(W)] 
target_set = set()
for i in range(M):
    h,w = map(int, input().split())
    h_dict[h].add(w)
    w_dict[w].add(h)
    target_set.add((h,w))
   
h_len_list = [0]+[len(h_dict[i]) for i in range(1,H+1)]
w_len_list = [0]+[len(w_dict[i]) for i in range(1,W+1)]

maxlen_h_value = max(h_len_list)
maxlen_w_value = max(w_len_list)
h_max_index = [i for i, x in enumerate(h_len_list) if x == max(h_len_list)]
w_max_index = [i for i, x in enumerate(w_len_list) if x == max(w_len_list)]

#print(h_len_list)
#print(w_len_list)
ans = 0
for i in h_max_index:
    for j in w_max_index:
        #print(i,j)
        if j not in h_dict[i]:
            print(maxlen_h_value + maxlen_w_value)
            exit()

print(maxlen_h_value + maxlen_w_value-1)

Submission status: Time Limit Exceeded

Solution code:
line1 = input()
aryLine1 = line1.split()
H = int(aryLine1[0]);
W = int(aryLine1[1]);
M = int(aryLine1[2]);

bomb = [[0 for j in range(W)] for i in range(H)]

#print(bomb)
hbomb = [0] * H
wbomb = [0] * W

for i in range(0, M):
    line = input()
    aryLine = line.split()
    h = int(aryLine[0]);
    w = int(aryLine[1]);
    bomb[h-1][w-1] = 1
    hbomb[h-1] = hbomb[h-1] + 1
    wbomb[w-1] = wbomb[w-1] + 1

ans = 0

for i in range(0, H):
    for j in range(0, W):
        cnt = hbomb[i]
        cnt = cnt + wbomb[j] - bomb[i][j]
        if cnt > ans:
            ans = cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

ans = 0
for i in mode_h:
    for j in mode_w:
        if ans < h.count(i) + w.count(j):
            ans = h.count(i) + w.count(j)
            for k in range(M):
                if h[k] == i and w[k] == j:
                    ans -= 1
            if ans == H + W - 1 or ans == M or ans == h_max + w_max:
                print(ans)
                exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,N = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
from collections import Counter
B,C = Counter(),Counter()
maxB,maxC = 0,0
for a in A:
    B[a[0]] += 1
    C[a[1]] += 1
for b in B:
    if maxB<B[b]:maxB = B[b]
for c in C:
    if maxC<C[c]:maxC = C[c]
def ifmax(array,maxV):
    maxArray = []
    for v in array:
        if array[v] == maxV:maxArray.append(v)
    return maxArray

maxBs = ifmax(B,maxB)
maxCs = ifmax(C,maxC)
# print(B,C,maxBs,maxCs)

sum = B[maxBs[0]] + C[maxCs[0]]
def aaa():
    for b in maxBs:
        for c in maxCs:
            if [b,c] not in A:return 0
    return -1

print(sum+aaa())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop
def main():
    H, W, M = map(int, input().split())
    tate = [[0, set(), i] for i in range(H)]
    yoko = [[0, set(), i] for i in range(W)]
    for _ in range(M):
        (i, j) = map(int, input().split())
        p = (i-1, j-1)
        tate[i-1][0] += 1
        tate[i-1][1].add(p)
        yoko[j-1][0] += 1
        yoko[j-1][1].add(p)
    
    tate_cp = tate.copy()
    yoko_cp = yoko.copy()
    heapify(tate)
    heapify(yoko)
    tate_kouho = set()
    pre_count = None
    while True:
        try:
            (count, ps, i) = heappop(tate)
        except:
            break
        if pre_count is not None and pre_count > count:
            break
        tate_kouho.add(i)
        pre_count = count

    yoko_kouho = set()
    pre_count = None
    while True:
        try:
            (count, ps, i) = heappop(yoko)
        except:
            break
        if pre_count is not None and pre_count > count:
            break
        yoko_kouho.add(i)
        pre_count = count
    
    count = 0
    for i in tate_kouho:
        for j in yoko_kouho:
            tate_cp[i]
            yoko_cp[j]
            bombs = len(tate_cp[i][1] | yoko_cp[j][1])
            count = max(count, bombs)

    print(count)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]
Tr=[0 for _ in range(H+1)]
Tc=[0 for _ in range(W+1)]
for i in range(M):
    Tr[s[i][0]]+=1
    Tc[s[i][1]]+=1
mr=max(Tr)
mc=max(Tc)
Mr=[i for i,x in enumerate(Tr) if x==mr]
Mc=[i for i,x in enumerate(Tc) if x==mc]

ans=0
for i in range(len(Mr)):
    for j in range(len(Mc)):
        if not ([Mr[i],Mc[j]] in s):
            ans=mr+mc
            break
    else:
        continue
    break
if ans==0:
    ans=mr+mc-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
H,W,M=map(int,input().split())
hh=[]
ww=[]
cord=[]
for i in range(M):
    h,w=map(int,input().split())
    hh.append(h)
    ww.append(w)
    cord.append([h,w])

cch=collections.Counter(hh)
ccw=collections.Counter(ww)

countinglisth=cch.most_common()
countinglistw=ccw.most_common()

naxh=countinglisth[0][1]
naxw=countinglistw[0][1]

for i in range(len(countinglisth)):
    for j in range(len(countinglistw)):
        if countinglisth[i][1]==naxh and countinglistw[j][1]==naxw:
            temp=[countinglisth[i][0],countinglistw[j][0]]
            if not( temp in cord):
                print(naxh+naxw)
                exit()
print(naxh+naxw-1)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Bom_list = list()
Y_list = list()
X_list = list()

for _ in range(M):
    Bom = list(map(int,input().split()))
    Bom_list.append(Bom)
    Y_list.append(Bom[0])
    X_list.append(Bom[1])

Y_counter = collections.Counter(Y_list)
X_counter = collections.Counter(X_list)

set_Y = list(set(Y_list))
set_X = list(set(X_list))
len_set_Y = len(set_Y)
len_set_X = len(set_X)

max_Y_num = 0 
max_X_num = 0
max_Y_list = list()
max_X_list = list()

for i in range(len_set_Y):
    if max_Y_num < Y_counter[set_Y[i]]:
        max_Y_list.clear()
        max_Y_num = Y_counter[set_Y[i]]
        max_Y_list.append(set_Y[i])
    elif max_Y_num == Y_counter[set_Y[i]]:
        max_Y_list.append(set_Y[i])
        max_Y_num = Y_counter[set_Y[i]]

for i in range(len_set_X):
    if max_X_num < X_counter[set_X[i]]:
        max_X_list.clear()
        max_X_num = X_counter[set_X[i]]
        max_X_list.append(set_X[i])
    elif max_X_num == X_counter[set_X[i]]:
        max_X_list.append(set_X[i])
        max_X_num = X_counter[set_X[i]]


# for i in range(len_set_Y):
#     if max_Y_num == Y_counter[set_Y[i]]:
#         max_Y_list.append(set_Y[i])

# for i in range(len_set_X):
#      if max_X_num == X_counter[set_X[i]]:
#          max_X_list.append(set_X[i])

ans = 0

for i in max_Y_list:
    for j in max_X_list:
        if [i,j] in Bom_list:
            ans = max_Y_num + max_X_num - 1
        else:
            ans = max_Y_num + max_X_num
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().strip().split())
h=[0 for _ in range(H)]
w=[0 for _ in range(W)]

dp=[[0 for _ in range(W)] for _ in range(H)]
for m in range(M):
    i,j=map(int,input().strip().split())
    dp[i-1][j-1]=1
    h[i-1]+=1
    w[j-1]+=1

h_max=0
hmax_l=[]
for i in range(H):
    if h_max==h[i]:
        hmax_l.append(i+1)
    elif h_max<h[i]:
        h_max=h[i]
        hmax_l=[]
        hmax_l.append(i+1)
w_max=0
wmax_l=[]
for i in range(W):
    if w_max==w[i]:
        wmax_l.append(i+1)
    elif w_max<w[i]:
        w_max=w[i]
        wmax_l=[]
        wmax_l.append(i+1)

d=True
for i in range(len(hmax_l)):
    for j in range(len(wmax_l)):
        if dp[hmax_l[i]-1][wmax_l[j]-1]==0:
            d=False
            break

ans=max(h)+max(w) if d==False else max(h)+max(w)-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Bom_list = list()
Y_list = list()
X_list = list()

for _ in range(M):
    Bom = list(map(int,input().split()))
    Bom_list.append(Bom)
    Y_list.append(Bom[0])
    X_list.append(Bom[1])

Y_counter = collections.Counter(Y_list)
X_counter = collections.Counter(X_list)

set_Y = list(set(Y_list))
set_X = list(set(X_list))
len_set_Y = len(set_Y)
len_set_X = len(set_X)

max_Y_num = 0 
max_X_num = 0

for i in range(len_set_Y):
    if max_Y_num < Y_counter[set_Y[i]]:
        max_Y_num = Y_counter[set_Y[i]]
    
for i in range(len_set_X):
     if max_X_num < X_counter[set_X[i]]:
         max_X_num = X_counter[set_X[i]]

max_Y_list = list()
max_X_list = list()

for i in range(len_set_Y):
    if max_Y_num == Y_counter[set_Y[i]]:
        max_Y_list.append(set_Y[i])

for i in range(len_set_X):
     if max_X_num == X_counter[set_X[i]]:
         max_X_list.append(set_X[i])

ans = 0

for i in max_Y_list:
    for j in max_X_list:
        if [i,j] in Bom_list:
            ans = max_Y_num + max_X_num - 1
        else:
            ans = max_Y_num + max_X_num
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
A=[]
B=[]
C=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
    C.append([a,b])
import collections
c = collections.Counter(A)
d = collections.Counter(B)
e =[i[0] for i in c.items() if i[1] == c.most_common()[0][1]]
f =[i[0] for i in d.items() if i[1] == d.most_common()[0][1]]
g =c.most_common()[0][1]+d.most_common()[0][1]
for p in range(len(e)):
    for k in range(len(f)):
        if [e[p],f[k]] not in C:
            print(g)
            exit()
print(g-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = [0 for _ in range(H)]
countw = [0 for _ in range(W)]
for _ in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1


maxh = max(counth)
maxw = max(countw)

counth = deque(counth)
countw = deque(countw)

index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
lenh = len(index_h)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
    lenw = len(index_w)
    if lenh*lenw > M:
      print(maxh + maxw)
      exit()    

ans = maxh + maxw - 1
for h in index_h:
  for w in index_w:
    if grid[h][w] == 0:
      ans += 1
      break
  else:
    continue
  break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0] * (H + 1)
w = [0] * (W + 1)
bombs = [[] for i in range(H + 1)]
hmax = 0
wmax = 0
hsrch = []
wsrch = []
for i in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    if h[x] > hmax:
        hmax = h[x]
        hsrch = [x]
    elif h[x] == hmax:
        hsrch.append(x)

    w[y] += 1
    if w[y] > wmax:
        wmax = w[y]
        wsrch = [y]
    elif w[y] == wmax:
        wsrch.append(y)
        
    bombs[x].append(y)

ans = 0
max = 0
for x in hsrch:
    for y in wsrch: 
        ans = h[x] + w[y]
        if ans > max:
            max = ans - 1 if y in bombs[x] else ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
hl = [0] * h
wl = [0] * w
dic = set()
for i in range(m):
  x,y = map(int, input().split())
  dic.add((x,y))
  hl[x-1] += 1
  wl[y-1] += 1

h_max = max(hl)
r = [i for i in range(h) if hl[i] == h_max]
w_max = max(wl)
c = [i for i in range(w) if wl[i] == w_max]

flg = 0
for rc in r:
  for cc in c:
    if (rc+1,cc+1) not in dic:
      flg = 1
      
if flg == 0:
  print(h_max + w_max - 1)
else:
  print(h_max + w_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return False


maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
k = 0
while k < H:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while k < W:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  for K in kouho:
    if binary_search(bomb, K):
      continue
    else:
      ans += 1
      break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
H, W, M = map(int, input().split())
bomb = []
heapq.heapify(bomb)
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  heapq.heappush(bomb, h+ w*H)
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
k = 0
while k < H:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while k < W:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  kouho = []
  heapq.heapify(kouho)
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      heapq.heappush(kouho, h+ H*w)
  B = heapq.heappop(bomb)
  K = heapq.heappop(kouho)
  while True:
    if B > K:
      ans += 1
      break
    elif B == K:
      if len(kouho) == 0:
        break
      else:
        K = heapq.heappop(kouho)
    else:
      if len(bomb) == 0:
        ans += 1
        break
      else:
        B = heapq.heappop(bomb)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def abc176_e():
    h, w, m = map(int, input().split())
    ch = [0]*h
    cw = [0]*w
    bs = dict()
    for _ in range(m):
        hi, wi = map(lambda x: int(x)-1, input().split())
        ch[hi] += 1
        cw[wi] += 1
        bs[(hi,wi)] = 1
    mch = max(ch)
    mcw = max(cw)
    if mch == h and mcw == w:
        ans = h + w - 1
    else:
        flag = False
        for i in [x for x in range(h) if ch[x] == mch]:
            for j in [x for x in range(w) if cw[x] == mcw]:
                if bs.get((i,j)) == None:
                    flag = True
                    break
            if flag: break
        if flag: ans = mch + mcw
        else: ans = mch + mcw - 1
    print(ans)

if __name__ == '__main__':
    abc176_e()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = list(map(int,input().split()))
rows = [0]*h
cols = [0]*w
bomb = [0]*m

for i in range(m):
    x,y = [int(i)-1 for i in input().split()]
    rows[x] += 1; cols[y] += 1
    bomb[i] = [x,y]

hmax = max(rows); wmax = max(cols); ans = hmax+wmax

hsearch = set(); wsearch = set()
for i in range(m):
    x,y = bomb[i]
    if rows[x] == hmax: hsearch.add(x)
    if cols[y] == wmax: wsearch.add(y)

if m < len(hsearch)*len(wsearch):
    flag = True
else:
    srows = list(hsearch)
    scols = list(wsearch)
    search_table = [[True for _ in range(len(scols))] for _ in range(len(srows))]
    for i in range(m):
        x,y = bomb[i]
        if x in srows and y in scols:
            search_table[srows.index(x)][scols.index(y)] = False

    flags = [True if sum(i)>0 else False for i in search_table]
    flag = any(flags)

print(ans if flag else ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0] * (H + 1)
w = [0] * (W + 1)
bombs = [[] for i in range(H + 1)]
for i in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    bombs[x].append(y)

hmax = max(h)
wmax = max(w)
hsrch = []
wsrch = []
for i in range(len(h)):
    if h[i] == hmax:
        hsrch.append(i)
for i in range(len(w)):
    if w[i] == wmax:
        wsrch.append(i)

ans = 0
max = 0
for x in hsrch:
    for y in wsrch: 
        ans = h[x] + w[y]
        if ans > max:
            max = ans - 1 if y in bombs[x] else ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)
# print('====')

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        if [h_ix, w_ix] in HW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0] * (H + 1)
w = [0] * (W + 1)
bombs = {}
for i in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    if x in bombs:
        bombs[x].append(y)
    else:
        bombs[x] = [y]

hmax = max(h)
wmax = max(w)
hsrch = []
wsrch = []
for i in range(len(h)):
    if h[i] == hmax:
        hsrch.append(i)
for i in range(len(w)):
    if w[i] == wmax:
        wsrch.append(i)

ans = 0
max = 0
for x in hsrch:
    for y in wsrch: 
        ans = h[x] + w[y]
        if ans > max:
            max = ans - 1 if y in bombs[x] else ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
# HW.sort()
# print(*HW,sep='\n')
# print(HW)
# print('---')

# 個:h_ix
# 0: -
# 1: 2
# 2: 1
# 3: -    <- W
# 個:w_ix
# 0: -
# 1: 1,2,3
# 2: -    <- H

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# sum_h.sort(reverse=True)
# sum_w.sort(reverse=True)
# print(HW)
# print(sum_h)
# print(sum_w)
# print('---')

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)

max_num = -1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        if [h_ix, w_ix] in HW:
            num -= 1
        max_num = max(max_num, num)
print(max_num)