Problem:


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, M = list(map(int, input().split()))
row = np.zeros(H)
col = np.zeros(W)
maps = np.zeros((M, 2), dtype=np.int64)
for i in range(M):
    h, w =list(map(int, input().split()))
    row[h-1] += 1
    col[w-1] += 1
    maps[i] = [h - 1, w - 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 not np.any(np.all(maps == [i, j], axis = 1)):
            d = 0
            break
    if d == 0:
        break

print(int(rowMax + colMax - d))

Submission status: Time Limit Exceeded

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

H, W, M = map(int, input().split())
tate = [0] * H
yoko = [0] * W
S = []

for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1] += 1
    S.append([h-1, w-1])


yoko_max = max(yoko)
yoko_index = []
tate_max = max(tate)
tate_index = []

for i in range(len(yoko)):
    if yoko[i] == yoko_max: yoko_index.append(i)

for i in range(len(tate)):
    if tate[i] == tate_max: tate_index.append(i)

flag = True

for i in range(len(yoko_index)):
    for j in range(len(tate_index)):
        if [tate_index[j], yoko_index[i]] in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

cm = max(col)
rm = max(row)
ri = [x for x,y in enumerate(row) if y == rm]
ci = [x for x,y in enumerate(col) if y == cm]
ans = -1
for c in ci:
  for r in ri:
    if c not in set(rn[r]):
      ans = max(ans,cm+rm)
      print(ans)
      exit()
ans = cm+rm-1
print(ans)

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)]
B=set()

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    B.add((hi,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)):
        if (h_max[ii]+1,w_max[jj]+1) not in B:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h = max(h_scores)
max_w = max(w_scores)
max_h_poss = [i for i,v in enumerate(h_scores) if v == max_h]
max_w_poss = [i for i,v in enumerate(w_scores) if v == max_w]

out_pos_count = 0 

c = False

for i in max_h_poss:
    for j in max_w_poss:
        if (i,j) not in record:
            c = True        

if c:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
r=dict()
c=dict()
pos=[]
rmax=0
cmax=0
for i in range(m):
    row,col=map(int,input().split())
    if(row in r):
        r[row]+=1
        rmax=max(r[row],rmax)
    else:
        r[row]=1
        rmax=max(r[row],rmax)
    if(col in c):
        c[col]+=1
        cmax=max(c[col],cmax)
    else:
        c[col]=1
        cmax=max(c[col],cmax)
    pos.append(str(row)+str(col))
    
sorted(r.items(),key=lambda x:x[1])
sorted(c.items(),key=lambda x:x[1])
ans=-100
for i in r.keys():
    if(r[i]<rmax):
        continue
    for j in c.keys():
        if(c[j]<cmax):
            continue
        tmp=r[i]+c[j]
        if((str(i)+str(j)) in pos):
            tmp-=1
        ans=max(ans,tmp)
        
print(ans)

Submission status: Time Limit Exceeded

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

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

ans = 0
# print("ans:", ans)
for j in range(h):
    for i in range(w):
        if str(j)+str(i) in bomb_xy:
            temp_max = h_bomb[j] + w_bomb[i] - 1
        else:
            temp_max = h_bomb[j] + w_bomb[i]

        # print("temp:", temp_max)
        if temp_max > ans:
            ans = temp_max

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)]
ht = [0] * h
wt = [0] * w
for i in hw:
    ht[i[0]-1] += 1
    wt[i[1]-1] += 1
ans = 0
for i in range(h):
    for j in range(w):
        if [i+1, j+1] in hw:
            ans = max(ans, ht[i]+wt[j]-1)
        else:
            ans = max(ans, ht[i]+wt[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
A=[[0]*H]*W
Bomb_ls=[]
X=[0]*M
Y=[0]*M
for i in range(M):
  X[i],Y[i]=[int(x) for x in input().split()]
  Bomb_ls.append([X[i],Y[i]])
R=Counter(X).most_common()
C=Counter(Y).most_common()
score=R[0][1]+C[0][1]-1
while True:
  i=0
  while True:
    j=0
    if R[i][1]+C[j][1]<=score:
      break
    if not [R[i][0],C[j][0]] in Bomb_ls:
      score = max(R[i][1]+C[j][1],score)
  else:
    continue
  break
print(score)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
s = [[False] * w for _ in range(h)]
num_h = [0] * h
num_w = [0] * w
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    s[hi][wi] = True
    num_h[hi] += 1
    num_w[wi] += 1
max_h_list = []
max_h_val = 0
max_w_list = []
max_w_val = 0
for hi in range(h):
    if num_h[hi] > max_h_val:
        max_h_list = [hi]
        max_h_val = num_h[hi]
    elif num_h[hi] == max_h_val:
        max_h_list.append(hi)
for wi in range(w):
    if num_w[wi] > max_w_val:
        max_w_list = [wi]
        max_w_val = num_w[wi]
    elif num_w[wi] == max_w_val:
        max_w_list.append(wi)

if len(max_h_list) * len(max_w_list) > m:
    print(max_h_val + max_w_val)
    exit()
for max_hi in max_h_list:
    for max_wi in max_w_list:
        if s[max_hi][max_wi] == False:
            print(max_h_val + max_w_val)
            exit()
print(max_h_val + max_w_val - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

hmax=max(hd.values())
wmax=max(wd.values())
max_h_list=[]
max_w_list=[]
for k in hd.keys():
    if hd[k]==hmax:
        max_h_list.append(k)

for k in wd.keys():
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, M = LI()
    hw = [tuple(LI()) for _ in range(M)]

    cnt_h = collections.Counter([h for h, w in hw])
    cnt_w = collections.Counter([w for h, w in hw])

    max_h = max(cnt_h.values())
    max_w = max(cnt_w.values())
    max_h_k = [k for k, v in cnt_h.items() if v == max_h]
    max_w_k = [k for k, v in cnt_w.items() if v == max_w]

    # 縦横のターゲット数最大の座標に置く
    # そのような座標がターゲット上ならば、縦横ターゲット数から1を引く
    is_on_target = True
    for i, j in itertools.product(max_h_k, max_w_k):
        if (i, j) not in hw:
            is_on_target = False
            break

    if is_on_target:
        ans = max_h + max_w - 1
    else:
        ans = max_h + max_w
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:

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

for i in range(m):
    a, b = map(int, input().split())
    tate[a] += 1
    yoko[b] += 1
    box.append([a,b])
tmax = max(tate)
ymax = max(yoko)
tbox = [i for i, v in enumerate(tate) if v == tmax]
ybox = [i for i, v in enumerate(yoko) if v == ymax]

flag = True
for i in tbox:
    for j in ybox:
        if not([i,j] in box):
           flag = False
#print(tmax,ymax,tbox,ybox,flag,box)
if flag:
    print(tmax + ymax - 1)
else:
    print(tmax + ymax)

Submission status: Time Limit Exceeded

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

area = []
w_list = []

max = 0


for i in range(h):
    w_list = []
    for j in range(w):
        w_list.append(".")

    area.append(w_list)

for num in range(m):
    t_h, t_w = map(int, input().split())

    area[t_h-1][t_w-1] = "#"


for i in range(h):
    for j in range(w):
        count = 0
        for width in range(w):
            if area[i][width] == "#":
                count += 1
        for height in range(h):
            if area[height][j] == "#":
                count += 1

        if area[i][j] == "#":
            count -= 1

        if count > max:
            max = count


print(max)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
lsx = [0] + [0]*H
lsy = [0] + [0]*W
lsxy = []
for i in range(M):
    x,y = map(int,input().split())
    lsx[x] += 1
    lsy[y] += 1
    lsxy.append([x,y])
maxx = max(lsx)
maxy = max(lsy)
lsmaxx = [i for i, x in enumerate(lsx) if x == maxx]
lsmaxy = [i for i, x in enumerate(lsy) if x == maxy]
lenlen = len(lsmaxx)*len(lsmaxy)
factor = 1
for i in lsmaxx:
    for j in lsmaxy:
        if not [i,j] in lsxy:
            factor = 0
            break
    if factor == 0:
        break
print(maxx+maxy-factor)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
l=[]
out=0
o=0
hb=[]
wb=[]
for i in range(h):
    hb.append([0,i+1])
for i in range(w):
    wb.append([0,i+1])

bo=[]
for i in range(m):
    a,b=list(map(int, input("").split()))
    hb[a-1][0]+=1
    wb[b-1][0]+=1
    bo.append([a,b])
hb.sort()
wb.sort()
for i in hb:
    for j in wb:
        o=i[0]+j[0]
        if [i[1],j[1]] in bo:
            o-=1
        #print([i[1],j[1]] ,o)
        if o>out:
            out=o
print(out)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

h, w, m = (int(x) for x in input().split())
H = [0] * h
W = [0] * w
HW = []
for _ in range(m):
    h_, w_ = (int(x) - 1 for x in input().split())
    HW.append((h_, w_))
    H[h_] += 1
    W[w_] += 1
hmax = max(H)
wmax = max(W)
hindex = []
windex = []
ans = hmax + wmax - 1

HW.sort(key=itemgetter(0, 1))
for y in range(h):
    if H[y] == hmax:
        hindex.append(y)
for x in range(w):
    if W[x] == wmax:
        windex.append(x)

HW_set = set(HW)
for y in hindex:
    for x in windex:
        if not (y, x) in HW_set:
            ans = hmax + wmax

print(ans)

Submission status: Time Limit Exceeded

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

X = [0] * H
Y = [0] * W
 
C = {}
for i in range(H):
    for j in range(W):
        C[(i, j)] = False
A = []
m = M
while m:
    m -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    C[(x, y)] = True
    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 C[(i, j)]: ans = True
        
cnt = xm + ym         
print(cnt if ans else cnt - 1)

Submission status: Time Limit Exceeded

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

bomb = []
for i in range(m):
    bomb.append(list(map(int, input().split())))
    
sum_hor, sum_ver = {}, {}
for i in range(m):
    h_i = bomb[i][0]-1
    w_i = bomb[i][1]-1
    if h_i not in sum_hor:
        sum_hor[h_i] = 1
    else:
        sum_hor[h_i] += 1
    if w_i not in sum_ver:
        sum_ver[w_i] = 1
    else:
        sum_ver[w_i] += 1

cost = []
for i in sum_hor.keys():
    for j in sum_ver.keys():
        if [i+1, j+1] in bomb:
            cost.append(sum_hor[i] + sum_ver[j] - 1)
        else:
            cost.append(sum_hor[i] + sum_ver[j])
print(max(cost))

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


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

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

    columnSumList: List[int] = []
    rowSumList: List[int] = []
    for i in range(H):
        rowSumList.append(0)
    for i in range(W):
        columnSumList.append(0)

    # currentCod: Cod = (0, 0)
    # currentSum = 0
    # oldList: List[Cod] = []
    for item in codList:
        columnSumList[item[1] - 1] += 1
        rowSumList[item[0] - 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)


def countBom(
    cod: Cod, rowSumList: List[int], columnSumList: List[int], codList: List[Cod]
) -> int:
    itemSum = rowSumList[cod[0] - 1] + columnSumList[cod[1] - 1]
    if cod in codList:
        return itemSum - 1
    else:
        return itemSum


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    B.append((hi,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)):
        if (h_max[ii]+1,w_max[jj]+1) not in B:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)

Submission status: Time Limit Exceeded

Solution code:
#E
import numpy as np
H,W,M=map(int,input().split())
arr=np.array([[0 for _ in range(W)] for i in range(H)])
h_arr=[]
w_arr=[]
for _ in range(M):
    h,w=map(int,input().split())
    arr[h-1][w-1]=int(1)
    h_arr.append(h-1)
    w_arr.append(w-1)
h_arr=list(set(h_arr))
w_arr=list(set(w_arr))
ans=[]
for i in h_arr:
    for j in w_arr:
        num=np.sum(arr[i,:])+np.sum(arr[:,j])
        if arr[i][j]==1:
            num-=1
        #print(np.sum(arr[i,:]))
        #print(np.sum(arr[:,j]))
        ans.append(num)
    
        


#print(arr)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

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

ans=float('inf')


for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)

Submission status: Time Limit Exceeded

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

maxh=maxw=0
qh=[]
qw=[]
for i in range(H):
  maxh=max(maxh, sumh[i])
for i in range(H):
  if maxh==sumh[i]:
    qh.append(i)

for i in range(W):
  maxw=max(maxw, sumw[i])
for i in range(W):
  if maxw==sumw[i]:
    qw.append(i)

#print(s,H,W,sumh,sumw,qh,qw)
for i in qh:
  for j in qw:
    if j not in s[i]:
      print(maxh+maxw)
      exit()

print(maxh+maxw-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def argmax_poss(a):
    if len(a) == 0:
        return []
    all_ = [0]
    max_ = a[0]
    for i in range(1, len(a)):
        if a[i] > max_:
            all_ = [i]
            max_ = a[i]
        elif a[i] == max_:
            all_.append(i)
    return all_

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

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h_poss = argmax_poss(h_scores)
max_w_poss = argmax_poss(w_scores)

out_pos_count = 0 

c = False

for i in max_h_poss:
    for j in max_w_poss:
        if (i,j) not in record:
            c = True        

if c:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[[0 for i in range(330000)] for j in range(330000)]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW[h][w]+=1

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)

import sys
for i in range(len(LY)):
    for j in range(len(LX)):
        if not HW[LY[i]][LX[j]]:
            print(MY+MX)
            sys.exit()

print(MY+MX-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int, input().split())
hh=[0 for i in range(H)]
ww=[0 for j in range(W)]
cord=[[False for i in range(W)]for j in range(H)]
for i in range(M):
    h,w=map(int,input().split())
    cord[h-1][w-1]=True
    hh[h-1]+=1
    ww[w-1]+=1
mxh=max(hh)
mxw=max(ww)
mh=[i for i,x in enumerate(hh)if x==mxh]
mw=[i for i,x in enumerate(ww)if x==mxw]
for mhs in mh:
    for mws in mw:
        if not(cord[mhs][mws]):
            print(mxh+mxw)
            exit()
print(mxh+mxw-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
points = []
xs = {}
ys = {}
points = set()
for i in range(m):
    x,y = map(int,input().split())
    points.add(str(x) + str(y))
    if xs.get(str(x)):
        xs[str(x)] += 1
    else:
        xs[str(x)] = 1
    if ys.get(str(y)):
        ys[str(y)] += 1
    else:
        ys[str(y)] = 1
max_x = [k for k, v in xs.items() if v == max(xs.values())]
max_y = [k for k, v in ys.items() if v == max(ys.values())]
boolen = 0
points = set(points)
for x in max_x:
    for y in max_y:
        if str(x) + str(y) not in points:
            boolen = 1
            break
if boolen == 0:
    print(xs[max_x[0]] + ys[max_y[0]]-1)
else:
    print(xs[max_x[0]] + ys[max_y[0]])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]
    
    
 
    
 
    bh_destroy = bomb_most_h[1]
    
 
    bw_destroy = bomb_most_w[1]
    
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]
 
    
    ans = 0
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if [bh,bw] in BOMB_HW:
                ans = max(bh_destroy+bw_destroy-1,ans)
            else:
                ans = max(bh_destroy+bw_destroy,ans)
    print(ans)
    
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
boms = [[0,0] for i in range(m)]
Hs = [0] * h
Ws = [0] * w
for i in range(m):
  _h, _w = map(int, input().split())
  boms[i][0] = _h - 1
  boms[i][1] = _w - 1
  Hs[_h - 1] += 1
  Ws[_w - 1] += 1
Hmax = max(Hs)
Hcount = Hs.count(Hmax)
Wmax = max(Ws)
Wcount = Ws.count(Wmax)
Hindexs = [0] * Hcount
Windexs = [0] * Wcount
hcount = 0
wcount = 0
for i in range(h):
  if Hs[i] == Hmax:
    Hindexs[hcount] = i
    hcount += 1
for i in range(w):
  if Ws[i] == Wmax:
    Windexs[wcount] = i
    wcount += 1
count = 0
for bom in boms:
  if (bom[0] in Hindexs) and (bom[1] in Windexs):
    count += 1
if count == len(Hindexs) * len(Windexs):
  print(Hmax + Wmax - 1)
else:
  print(Hmax + Wmax)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for h in h_max_list:
    for w in w_max_list:
        if t[h][w] == 0:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

Submission status: Time Limit Exceeded

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

import collections
h, w, m = map(int, input().split())
hw =[list(map(int, input().split())) for i in range(m)]
hh = [0]*m
ww = [0]*m
for i in range(m):
  hh[i] = hw[i][0]
  ww[i] = hw[i][1]


hcnt = collections.Counter(hh).most_common()[0][1]
wcnt = collections.Counter(ww).most_common()[0][1]
ans = hcnt +wcnt

hhh = []
www = []
for i in range(len(collections.Counter(hh))):
  if hcnt == collections.Counter(hh).most_common()[i][1]:
    hhh.append(collections.Counter(hh).most_common()[i][0])
for i in range(len(collections.Counter(ww))):
  if wcnt == collections.Counter(ww).most_common()[i][1]:
    www.append(collections.Counter(ww).most_common()[i][0])

    
newhw = [[i,j] for i in hhh for j in www]
if all(i in hw for i in newhw):
  ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


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 = [i for i, v in enumerate(Mh) if v == nh]
    lw = [i for i, v in enumerate(Mw) if v == nw]

    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:
h, w, m = map(int, input().split())

h_bomb = [0 for _ in range(h)]
w_bomb = [0 for _ in range(w)]

bomb_xy = {}
for ij in range(m):
    y, x = map(int, input().split())
    h_bomb[y-1] += 1
    w_bomb[x-1] += 1
    bomb_xy[str(y-1)+str(x-1)] = 1

h_max = max(h_bomb)
h_max_index = [i for i, y in enumerate(h_bomb) if y == h_max]

ans = 0
# print("ans:", ans)
for j in h_max_index:
    for i in range(w):
        if str(j)+str(i) in bomb_xy:
            temp_max = h_bomb[j] + w_bomb[i] - 1
        else:
            temp_max = h_bomb[j] + w_bomb[i]

        # print("temp:", temp_max)
        if temp_max > ans:
            ans = temp_max

print(ans)

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)]
    regy = [0]*h
    regx = [0]*w
    for x in s:
        regy[x[0]] += 1
        regx[x[1]] += 1
    maxy = 0
    indy = []
    for i in range(h):
        if maxy < regy[i]:
            indy = [i]
            maxy = regy[i]
        elif maxy == regy[i]:
            indy.append(i)
    maxx = 0
    indx = []
    for i in range(w):
        if maxx < regx[i]:
            indx = [i]
            maxx = regx[i]
        elif maxx == regx[i]:
            indx.append(i)

    ans = maxy + maxx
    tmp = 1
    if len(indy)*len(indx) > m:
        tmp = 0
    else:
        for y in indy:
            for x in indx:
                if [y, x] not in s[:]:
                    tmp = 0
    print(ans - tmp)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

h = [0] * H
w = [0] * W

g = [[False] * W for _ in range(H)]

for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    g[Th - 1][Tw - 1] = True

ans = max(h) + max(w)

index_h = [n for n, v in enumerate(h) if v == max(h)]
index_w = [n for n ,v in enumerate(w) if v == max(w)]

ans1 = 1
for ih in index_h:
    for iv in index_w:
        if g[ih][iv] is False:
            ans1 = 0
            break
    else:
        break

ans -= ans1


print(ans)

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-1, w-1))
coords = set(coords)

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

# 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

from itertools import product
# print('coords:', coords)
indexes = set(list(product(row_indexes, col_indexes)))
# print('indexes: ', indexes)
# print('intersection: ', coords.intersection(set(list(product(row_indexes, col_indexes)))))
# print('dif: ', indexes - coords)
if len(indexes-coords) > 0:
    print(int(col_sums.max() + row_sums.max()))
else:
    print(int(col_sums.max() + row_sums.max()) - 1)

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