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

gh = {i:[] for i in range(h)}
gw = {i:[] for i in range(w)}

for _h, _w in hw:
    gh[_h-1].append(_w-1)
    gw[_w-1].append(_h-1)
    
ansh = 0
posh = {}
answ = 0
posw = {}
for k,v in gh.items():
    if len(v) >= ansh:
        ansh = len(v)
        
for k,v in gh.items():
    if len(v) == ansh:
        posh[k]=k
        
for k,v in gw.items():
    if len(v) >= answ:
        answ = len(v)
        
for k,v in gw.items():
    if len(v) == answ:
        posw[k]=k
        
hoge = True
for i in posh:
    for j in posw:
        if i not in gw[j]:
            hoge = False
            
if hoge:
    print(ansh+answ-1)
else:
    print(ansh+answ)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
table=[]
H=[0]*h
W=[0]*w
li_h=[]
li_w=[]

for i in range(m):
    h1,w1=list(map(int,input().split()))
    table.append((h1-1,w1-1))
    H[h1-1]+=1
    W[w1-1]+=1

h_flag=0
w_flag=0



Hh=[i for i, x in enumerate(H) if x == max(H)]
Ww=[i for i, x in enumerate(W) if x == max(W)]

cnt=0

for (h, w) in table:
    if H[h] == max(H) and W[w] == max(W):
        cnt += 1

if cnt<len(Hh)*len(Ww):
    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()))

hw = []
w = [0] * (W+1)
h = [0] * (H+1)
hw = [list(map(int,input().split())) for i in range(M)]
for h_i, w_j in hw:
    # h_i, w_j = map(int, input().split())
    # hw.append([h_i-1, w_j-1])
    h[h_i] += 1
    w[w_j] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not([i,j] in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for i in xs:
        for j in ys:
            if(i not in bombs[j] ):
                return value
    return value-1

    """
    for i in range( H ):
        if(V_N[i]==max_y):
            for j in range( W ):
                if(W_N[j]==max_x and W_N[j] not in bombs[i] ):
                #if(W_N[j]==max_x and bombs[i][j] == 0 ):

                    return value

    return value-1
    """

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    """
    V_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    """
    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)


    """
    W_N_bomb.sort(key = lambda x: x[0])
    V_N_bomb.sort(key = lambda x: x[0])
    """

    print( solve(W_N, V_N, bombs, H, W) )

    """


    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ V_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = V_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])

    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, V_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = V_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break

    if(flag==True):
        print(value)
    else:
        print(value-1)
    """

Submission status: Time Limit Exceeded

Solution code:

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

hw = []
# w = np.zeros(3*10**5,dtype=np.int64)
# h = np.zeros(3*10**5,dtype=np.int64)
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not([i,j] in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)

Submission status: Time Limit Exceeded

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


# @njit(i8[:,:](i8[:,:],i8[:,:],i8))
# def calcBombT(hw,tar,M):
#     for i in range(M):
#         tar[hw[i,0]-1,hw[i,1]-1] = 1
#     return tar


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombR(hw,row,M):
    for i in range(M):
        row[hw[i,0]-1] += 1
    return row


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombC(hw,col,M):
    for i in range(M):
        col[hw[i,1]-1] += 1
    return col


# @njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8,i8,i8[:]))
def existNR(hw,indMR,indMC,NR,NC,Ntemp,cnt,check,temp):
    for i in range(NR):
        temp = np.array(np.where(hw[:,0] == indMR[i]+1)[0])
        Ntemp = temp.size
        cnt = 0
        Ntemp = loopjk(hw,indMR,indMC,NC,Ntemp,cnt,temp)
        if Ntemp == 0:
            check = 1
            break
    return check


@njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8[:]))
def loopjk(hw,indMR,indMC,NC,Ntemp,cnt,temp):
    for j in range(NC):
        cnt = 0
        for k in range(Ntemp):
            if hw[temp[k],1] != indMC[j]+1:
                cnt += 1
            if cnt == Ntemp:
                Ntemp = 0
                break
        if Ntemp == 0:
            break
    return Ntemp


# @njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8,i8,i8[:]))
def existNC(hw,indMR,indMC,NR,NC,Ntemp,cnt,check,temp):
    for j in range(NC):
        temp = np.array(np.where(hw[:,1] == indMC[j]+1)[0])
        Ntemp = temp.size
        cnt = 0
        Ntemp = loopik(hw,indMR,indMC,NR,Ntemp,cnt,temp)
        if Ntemp == 0:
            check = 1
            break
    return check


@njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8[:]))
def loopik(hw,indMR,indMC,NR,Ntemp,cnt,temp):
    for i in range(NR):
        cnt = 0
        for k in range(Ntemp):
            if hw[temp[k],0] != indMR[i]+1:
                cnt += 1
            if cnt == Ntemp:
                Ntemp = 0
                break
        if Ntemp == 0:
            break
    return Ntemp


def main():
    H,W,M = map(int,input().split())
    hw = [list(map(int,input().split())) for i in range(M)]
    hw = np.array(hw)

    # tar = np.zeros((H,W),dtype = int)
    row = np.zeros(H,dtype = int)
    col = np.zeros(W,dtype = int)

    # tar = calcBombT(hw,tar,M)
    row = calcBombR(hw,row,M)
    col = calcBombC(hw,col,M)

    MR = row.max()
    MC = col.max()

    indMR = np.where(row == MR)[0]
    indMC = np.where(col == MC)[0]

    indMR = np.array(indMR)
    indMC = np.array(indMC)

    NR = len(indMR)
    NC = len(indMC)

    if NR > NC:
        check = existNC(hw,indMR,indMC,NR,NC,1,0,0,np.array([0]))
    else:
        check = existNR(hw,indMR,indMC,NR,NC,1,0,0,np.array([0]))

    if check:
        res = MR + MC
    else:
        res = MR + MC - 1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hlist = [0] * H
wlist = [0] * W
hw = [[0 for _ in range(W)] for _ in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    hlist[h - 1] += 1
    wlist[w - 1] += 1
    hw[h - 1][w - 1] = 1

hmax = max(hlist)
wmax = max(wlist)
hmaxlist = [i for i, v in enumerate(hlist) if v == hmax]
wmaxlist = [i for i, v in enumerate(wlist) if v == wmax]
cnt = -1
for i in hmaxlist:
    bf = False
    for j in wmaxlist:
        if hw[i][j] != 1:
            cnt = 0
            bf = True
            break
    if bf:
        break

print(hmax + wmax + cnt)

Submission status: Time Limit Exceeded

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


# @njit(i8[:,:](i8[:,:],i8[:,:],i8))
# def calcBombT(hw,tar,M):
#     for i in range(M):
#         tar[hw[i,0]-1,hw[i,1]-1] = 1
#     return tar


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombR(hw,row,M):
    for i in range(M):
        row[hw[i,0]-1] += 1
    return row


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombC(hw,col,M):
    for i in range(M):
        col[hw[i,1]-1] += 1
    return col


# @njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8,i8,i8[:]))
def exist(hw,indMR,indMC,NR,NC,Ntemp,cnt,check,temp):
    for i in range(NR):
        temp = np.array(np.where(hw[:,0] == indMR[i]+1)[0])
        Ntemp = temp.size
        cnt = 0
        Ntemp = loopjk(hw,indMR,indMC,NC,Ntemp,cnt,temp)
        if Ntemp == 0:
            check = 1
            break
    return check


@njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8[:]))
def loopjk(hw,indMR,indMC,NC,Ntemp,cnt,temp):
    for j in range(NC):
        cnt = 0
        for k in range(Ntemp):
            if hw[temp[k],1] != indMC[j]+1:
                cnt += 1
            if cnt == Ntemp:
                Ntemp = 0
                break
        if Ntemp == 0:
            break
    return Ntemp


def main():
    H,W,M = map(int,input().split())
    hw = [list(map(int,input().split())) for i in range(M)]
    hw = np.array(hw)

    # tar = np.zeros((H,W),dtype = int)
    row = np.zeros(H,dtype = int)
    col = np.zeros(W,dtype = int)

    # tar = calcBombT(hw,tar,M)
    row = calcBombR(hw,row,M)
    col = calcBombC(hw,col,M)

    MR = row.max()
    MC = col.max()

    indMR = np.where(row == MR)[0]
    indMC = np.where(col == MC)[0]

    indMR = np.array(indMR)
    indMC = np.array(indMC)

    NR = len(indMR)
    NC = len(indMC)

    check = exist(hw,indMR,indMC,NR,NC,1,0,0,np.array([0]))

    if check:
        res = MR + MC
    else:
        res = MR + MC - 1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read

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

hw = []
# w = np.zeros(3*10**5,dtype=np.int64)
# h = np.zeros(3*10**5,dtype=np.int64)
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not([i,j] in hw):
            d = 0
    if d == 0:
        break
print(mxh_v+mxw_v-d)

Submission status: Time Limit Exceeded

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

gh = {i:[] for i in range(h+1)}
gw = {i:[] for i in range(w+1)}

for _h, _w in hw:
    gh[_h].append(_w)
    gw[_w].append(_h)
    
ansh = 0
posh = -1
answ = 0
posw = -1
for k,v in gh.items():
    if len(v) > ansh:
        ansh = len(v)
        posh = k
for k,v in gw.items():
    if [posh,k] in hw:
        if len(v)-1 > answ:
            answ = len(v)-1
            posw = k
    else:
        if len(v) > answ:
            answ = len(v)
            posw = k
            
print(ansh+answ)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PF[h, w] += 1

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()
most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = []
for x in frequency_h_list:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in frequency_w_list:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)

Submission status: Time Limit Exceeded

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


# @njit(i8[:,:](i8[:,:],i8[:,:],i8))
# def calcBombT(hw,tar,M):
#     for i in range(M):
#         tar[hw[i,0]-1,hw[i,1]-1] = 1
#     return tar


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombR(hw,row,M):
    for i in range(M):
        row[hw[i,0]-1] += 1
    return row


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombC(hw,col,M):
    for i in range(M):
        col[hw[i,1]-1] += 1
    return col


# @njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8,i8,i8[:]))
def exist(hw,indMR,indMC,NR,NC,Ntemp,cnt,check,temp):
    for i in range(NR):
        for j in range(NC):
            temp = np.array(np.where(hw[:,0] == indMR[i]+1)[0])
            Ntemp = temp.size
            cnt = 0
            Ntemp = loopk(hw,indMC,j,Ntemp,cnt,temp)
            if Ntemp == 0:
                break
        if Ntemp == 0:
            check = 1
            break
    return check


@njit(i8(i8[:,:],i8[:],i8,i8,i8,i8[:]))
def loopk(hw,indMC,j,Ntemp,cnt,temp):
    for k in range(Ntemp):
        if hw[temp[k],1] != indMC[j]+1:
            cnt += 1
        if cnt == Ntemp:
            Ntemp = 0
            break
    return Ntemp


def main():
    H,W,M = map(int,input().split())
    hw = [list(map(int,input().split())) for i in range(M)]
    hw = np.array(hw)

    # tar = np.zeros((H,W),dtype = int)
    row = np.zeros(H,dtype = int)
    col = np.zeros(W,dtype = int)

    # tar = calcBombT(hw,tar,M)
    row = calcBombR(hw,row,M)
    col = calcBombC(hw,col,M)

    MR = row.max()
    MC = col.max()

    indMR = np.where(row == MR)[0]
    indMC = np.where(col == MC)[0]

    indMR = np.array(indMR)
    indMC = np.array(indMC)

    NR = len(indMR)
    NC = len(indMC)

    check = exist(hw,indMR,indMC,NR,NC,1,0,0,np.array([0]))

    if check:
        res = MR + MC
    else:
        res = MR + MC - 1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = h.max()
mxw_v = w.max()
for i in np.where(h==mxh_v)[0]:
    for j in np.where(w==mxw_v)[0]:
        if not([i,j] in hw):
            d = 0
    if d == 0:
        break

print(mxh_v+mxw_v-d)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PHF = defaultdict(int)
PWF = defaultdict(int)
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PHF[h] += 1
    PWF[w] += 1
    PF[h, w] += 1

sorted_PHF = sorted(PHF.items(), key=lambda x: x[1], reverse=True)
sorted_PWF = sorted(PWF.items(), key=lambda x: x[1], reverse=True)
most_common_h_cnt = sorted_PHF[0][1]
most_common_w_cnt = sorted_PWF[0][1]

most_common_h_list = []
for x in sorted_PHF:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in sorted_PWF:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)

Submission status: Time Limit Exceeded

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


# @njit(i8[:,:](i8[:,:],i8[:,:],i8))
# def calcBombT(hw,tar,M):
#     for i in range(M):
#         tar[hw[i,0]-1,hw[i,1]-1] = 1
#     return tar


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombR(hw,row,M):
    for i in range(M):
        row[hw[i,0]-1] += 1
    return row


@njit(i8[:](i8[:,:],i8[:],i8))
def calcBombC(hw,col,M):
    for i in range(M):
        col[hw[i,1]-1] += 1
    return col


# @njit(i8(i8[:,:],i8[:],i8[:],i8,i8,i8,i8,i8,i8[:]))
def exist(hw,indMR,indMC,NR,NC,Ntemp,cnt,check,temp):
    for i in range(NR):
        for j in range(NC):
            temp = np.array(np.where(hw[:,0] == indMR[i]+1)[0])
            Ntemp = temp.size
            cnt = 0
            for k in range(Ntemp):
                if hw[temp[k],1] != indMC[j]+1:
                    cnt += 1
                if cnt == Ntemp:
                    check = 1
                    Ntemp = 0
                    break
            if Ntemp == 0:
                check = 1
                break
        if Ntemp == 0:
            check = 1
            break
    return check


def main():
    H,W,M = map(int,input().split())
    hw = [list(map(int,input().split())) for i in range(M)]
    hw = np.array(hw)

    # tar = np.zeros((H,W),dtype = int)
    row = np.zeros(H,dtype = int)
    col = np.zeros(W,dtype = int)

    # tar = calcBombT(hw,tar,M)
    row = calcBombR(hw,row,M)
    col = calcBombC(hw,col,M)

    MR = row.max()
    MC = col.max()

    indMR = np.where(row == MR)[0]
    indMC = np.where(col == MC)[0]

    indMR = np.array(indMR)
    indMC = np.array(indMC)

    NR = len(indMR)
    NC = len(indMC)

    check = exist(hw,indMR,indMC,NR,NC,1,0,0,np.array([0]))

    if check:
        res = MR + MC
    else:
        res = MR + MC - 1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
mxh_v = h.max()
mxw_v = w.max()
for i in np.where(h==mxh_v)[0]:
    for j in np.where(w==mxw_v)[0]:

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            d = 1
    if d == 1:
        break

print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
for i in np.where(h==h.max())[0]:
    for j in np.where(w==w.max())[0]:
        mxh_v = h[i]
        mxw_v = w[j]

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            d = 1
    if d == 1:
        break

print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
for i in np.where(h==h.max())[0]:
    for j in np.where(w==w.max())[0]:
        mxh_v = h[i]
        mxw_v = w[j]

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            break

print(a)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
MX=[0]*H
MY=[0]*W
MA=[0]*M

for i in range(M):
  x,y=map(int,input().split())
  x-=1
  y-=1
  MX[x]+=1
  MY[y]+=1
  MA[i]=(x,y)
xmax=max(MX)
ymax=max(MY)
ix=[x[0] for x in enumerate(MX) if x[1]==xmax]
iy=[x[0] for x in enumerate(MY) if x[1]==ymax]

if len(ix)*len(iy)>M:
  print(xmax+ymax)
else:
  for ixx in ix:
    for iyy in iy:
      if (ixx,iyy) not in MA:
        print(xmax+ymax)
        exit()
  
  print(xmax+ymax-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
for i in np.where(h==h.max())[0]:
    for j in np.where(w==w.max())[0]:
        mxh_v = h[i]
        mxw_v = w[j]

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)

print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()
most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = []
for x in frequency_h_list:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in frequency_w_list:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

contain_intersection = {}
for h in most_common_h_list:
    for w in most_common_w_list:
        contain_intersection[h, w] = False

for i in range(M):
    h, w = PH[i], PW[i]
    if (h, w) in contain_intersection:
        contain_intersection[h, w] = True
cnt = most_common_h_cnt + most_common_w_cnt
if all([contain_intersection[key] for key in contain_intersection]):
    cnt -= 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter, defaultdict
import itertools

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

d_h = deque()
d_w = deque()

dic = defaultdict(list)

for h, w in HW:
    d_h.append(h)
    d_w.append(w)
    dic[h].append(w)

# 出現頻度順にソート
c_h = Counter(d_h).most_common()
c_w = Counter(d_w).most_common()

# 登場頻度の一番高い回数
n_h = c_h[0][1]
n_w = c_w[0][1]

# 同率のものを数える
t_h = deque()
t_w = deque()

for k, v in c_h:
    if v == n_h:
        t_h.append(k)
    else:
        break

for k, v in c_w:
    if v == n_w:
        t_w.append(k)
    else:
        break


nn = len(t_h) * len(t_w)

ans = n_h + n_w
if nn <= M:
    q = set(list(itertools.product(t_h, t_w)))
    for h, w in q:
        if w not in dic[h]:
            break
    else:
        ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

h = [-1]
w = [-1]
hw = [[0 for _ in range(W + 1)]for _ in range(H + 1)]

for _ in range(M):
    hi, wi = map(int, input().split())
    h.append(hi)
    w.append(wi)
    hw[hi][wi] = 1

h_cnt = [0] * (H + 1)
w_cnt = [0] * (W + 1)
for i in range(1, M + 1):
    h_cnt[h[i]] += 1
    w_cnt[w[i]] += 1

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []

for i in range(1, H + 1):
    if h_cnt[i] == h_max:
        h_max_idx.append(i)

for i in range(1, W + 1):
    if w_cnt[i] == w_max:
        w_max_idx.append(i)

for i in h_max_idx:
    for j in w_max_idx:
        if hw[i][j] == 0:
            print(h_max + w_max)
            exit()

print(h_max + w_max - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools

import numpy as np


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

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    dh = defaultdict(list)
    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1
        dh[h - 1].append(w - 1)

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in itertools.product(ind_A, ind_B):
            if w not in dh[h]:
                break
        else:
            ans -= 1

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = [int(n) for n in input().split()]
H_freq = [0] * H
W_freq = [0] * W

coordinates = {}
for m in range(M):
    h, w = [int(n)-1 for n in input().split()]
    H_freq[h] += 1
    W_freq[w] += 1
    if h in coordinates.keys():
        coordinates[h].append(w)
    else:
        coordinates[h] = [w]

max_h = max(H_freq)
max_w = max(W_freq)
most_freqent_h = [i for i, h in enumerate(H_freq) if h == max_h]
most_freqent_w = [i for i, w in enumerate(W_freq) if w == max_w]

ans = 0
for h in most_freqent_h:
    for w in most_freqent_w:
        if w in coordinates[h]:
            ans = max_h + max_w - 1
        else:
            ans = max_h + max_w
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set
import array

# from typing import Sequence

Cod = Tuple[int, int]


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

    codList: array[Cod] = []
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.append(item)
        # codList.setdefault(h, {})
        # codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

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

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


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


def main():
    H, W, M = map(int, input().split())
    lh = [0] * H
    lw = [0] * W
    s = set()
    for _ in range(M):
        h, w = map(int, input().split())
        lh[h - 1] += 1
        lw[w - 1] += 1
        s.add((h-1, w-1))

    maxh = max(lh)
    maxw = max(lw)
    for i in range(H):
        if lh[i] !=maxh:
            continue
        for j in range(W):
            if lw[j] !=maxw:
                continue
            if (i,j) not in s:
                print(maxh+maxw)
                exit()

    print(maxh+maxw-1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

import numpy as np

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

A = np.zeros(H, dtype=np.int64)
B = np.zeros(W, dtype=np.int64)

for h, w in HW:
    A[h - 1] += 1
    B[w - 1] += 1

maxA = np.max(A)
maxB = np.max(B)

# 最大値を取るindex
ind_A = np.arange(H)[A == maxA]
ind_B = np.arange(W)[B == maxB]

# 解の候補の数
nn = len(ind_A) * len(ind_B)

# Mより候補の数のほうが多いとok
# 少ないときはM以下なので可算
ans = maxA + maxB
if nn <= M:
    for h, w in itertools.product(ind_A, ind_B):
        if [h + 1, w + 1] not in HW:
            break
    else:
        ans -= 1

print(ans)