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:
from collections import Counter
H,W,M=map(int,input().split())
Bomb_ls=[]
R=[0]*H
C=[0]*W
for i in range(M):
  X,Y=[int(x) for x in input().split()]
  Bomb_ls.append([X-1,Y-1])
  R[X-1]+=1
  C[Y-1]+=1
R_max=[i for i, x in enumerate(R) if x == max(R)]
C_max=[i for i, x in enumerate(C) if x == max(C)]
if len(R_max)*len(C_max)>M:
  print(max(R)+max(C))
else:
  score=-1
  for r in R_max:
    for c in C_max:
      if not [r,c] in Bomb_ls:
        score=0
        break
  print(max(R)+max(C)+score)

Submission status: Time Limit Exceeded

Solution code:
import pprint
H, W, M = map(int, input().split())
bombs = [[0 for _ in range(W)] for _ in range(H)]
hCount = [0]*H
vCount = [0]*W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1; w -= 1;
    hCount[h] += 1
    vCount[w] += 1
    bombs[h][w] = 1

hMax = max(hCount)
vMax = max(vCount)
hMaxIndex = [i for i, x in enumerate(hCount) if x==max(hCount)]
vMaxIndex = [i for i, x in enumerate(vCount) if x==max(vCount)]

ans = -1
for y in hMaxIndex:
    for x in vMaxIndex:
        if bombs[y][x]:
            ans = max(hMax + vMax - 1, ans)
        else:
            ans = max(hMax+vMax, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
Bomb_ls=[]
R=[0]*H
C=[0]*W
for i in range(M):
  X,Y=[int(x) for x in input().split()]
  Bomb_ls.append([X-1,Y-1])
  R[X-1]+=1
  C[Y-1]+=1

R_max=[i for i, x in enumerate(R) if x == max(R)]
C_max=[i for i, x in enumerate(C) if x == max(C)]
if len(R_max)*len(C_max)>M:
  print(max(R)+max(C))
else:
  score=-1
  for r in R_max:
    for c in C_max:
      if not [r,c] in Bomb_ls:
        score=0
        break
    else:
      continue
    break
  print(max(R)+max(C)+score)

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)
C=Counter(Y)
R_max = [letter for letter,count in R.most_common() if count == R.most_common()[0][1]]
C_max = [letter for letter,count in C.most_common() if count == C.most_common()[0][1]]
score=-1
if len(R_max)*len(C_max)>M:
  print(max(R.values())+max(C.values()))
else:
  score=-1
  for r in R_max:
    for c in C_max:
      if not [r,c] in Bomb_ls:
        score=0
        break
    else:
      continue
    break
  print(max(R.values())+max(C.values())+score)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
    hi, wi = map(int, input().split())
    a[hi-1][wi-1] = 1

mh = [sum(a[i][:]) for i in range(h)]
mw = [sum([r[i] for r in a]) for i in range(w)]
ans = max(mh) + max(mw)

mh = [i for i, v in enumerate(mh) if v == max(mh)]
mw = [i for i, v in enumerate(mw) if v == max(mw)]

flag = 0
for i in mh:
    for j in mw:
        if a[i][j] == 0:
            print(ans)
            exit()
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

h, w, m = map(int, input().split())
x = list(list(map(int, input().split())) for i in range(m))

#print(h, w, m, x)

#行検索
a_lis = []
for i in range(m):
    a_lis.append(x[i][0])
#print(a_lis)

#行の最大爆発個数,行数
a_cnt = cl.Counter(a_lis)
#print(a_cnt)
max_a = a_cnt.most_common()[0][1]

set_a_lis = [] #最大個数を満たすマスのリスト
for i in range(len(a_cnt)):
    if a_cnt.most_common()[i][1] == max_a:
        set_a_lis.append(a_cnt.most_common()[i][0])
#print(max_a, set_a_lis)


#列検索
b_lis = []
for i in range(m):
     b_lis.append(x[i][1])
#print(b_lis)

#列の最大爆発数
b_cnt = cl.Counter(b_lis)
#print(b_cnt)
max_b = b_cnt.most_common()[0][1]

set_b_lis = [] #最大個数を満たすマスのリスト
for i in range(len(b_cnt)):
    if b_cnt.most_common()[i][1] == max_b:
        set_b_lis.append(b_cnt.most_common()[i][0])
#print(max_b, set_b_lis)



#爆弾があるところにおいたら１を引く
flag = 0
for i in range(m):
    for j in range(len(set_a_lis)):
        for k in range(len(set_b_lis)):
            if x[i][0] == set_a_lis[j] and x[i][1] == set_b_lis[k]:
                flag += 1

#print(flag)
if flag == len(set_a_lis) * len(set_b_lis):
    ans = max_a + max_b - 1
else:
    ans = max_a + max_b

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bombs_h = [0] * H
bombs_w = [0] * W
S = [[] for _ in range(H)]
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    S[h].append(w)
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
p = 1
for i in hs:
    for j in ws:
        if j not in S[i]:
            p = 0
            break
ans = max_w + max_h - p
print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
A=dict()
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    if h-1 not in A:
        A[h-1]=[w-1]
    else:
        A[h-1].append(w-1)
    #A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

add=1
#A.sort()
for i in mh:
    if i not in A:
        add=0
        break
    else:
        for j in mw:
            if j not in A[i]:
                add=0
                break
        
    if add==0:break

ans-=add

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush


h,w,m=[int(x) for x in input().split()]

#defaultdictにすることにより後に使うmax関数のコストを削減
hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=[]
#O(M)
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.append([hi,wi])

#O(M)
hmax=max(hcnt.values())
wmax=max(wcnt.values())

#O(M)
hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

#O(M**2*)
ofst=-1
for i in hidx:
    for j in widx:
        if not [i,j] in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)

Submission status: Time Limit Exceeded

Solution code:
#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M

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

exist = [[False]*W for _ in range(H)]
for i in range(M):
    exist[h[i]][w[i]]=True

from collections import Counter
ch = Counter(h)
cw = Counter(w)

print( max(ch[x]+cw[y]-exist[x][y] for x in range(H) for y in range(W) ))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
S = [[0 for _ in range(W)] for i in range(H)]
bombs_h = [0] * H
bombs_w = [0] * W
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    S[h][w] = 1
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
p = 1
for i in hs:
    for j in ws:
        if S[i][j] == 0:
            p = 0
            break
ans = max_w + max_h - p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)

for _ in range(m):
    h_m, w_m = map(int, input().split())
    cnt_h[h_m - 1] += 1
    cnt_w[w_m - 1] += 1
    dic[(h_m - 1, w_m - 1)] += 1

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
    if max_h == cnt_h[i]:
        mh.append(i)

for i in range(w):
    if max_w == cnt_w[i]:
        mw.append(i)

flag = False
for i in mh:
    for j in mw:
        if dic[(i, j)] == 0:
            flag = True

if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
    hi, wi = map(lambda x:int(x) - 1, input().split())
    a[hi][wi] = 1

mh = [sum(a[i][:]) for i in range(h)]
mw = [sum([r[i] for r in a]) for i in range(w)]
s = [["B" for _ in range(w)] for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == 0:
            v = mh[i] + mw[j]
            s[i][j] = v
        else:
            v = mh[i] + mw[j] - 1

        if v >= ans:
            ans = v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)

for _ in range(m):
    h_m, w_m = map(int, input().split())
    cnt_h[h_m - 1] += 1
    cnt_w[w_m - 1] += 1
    dic[h_m - 1, w_m - 1] += 1

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
    if max_h == cnt_h[i]:
        mh.append(i)

for i in range(w):
    if max_w == cnt_w[i]:
        mw.append(i)

flag = False
for i in mh:
    for j in mw:
        if dic[i, j] == 0:
            flag = True

if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)

Submission status: Time Limit Exceeded

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

bom_H =defaultdict(int)
bom_W =defaultdict(int)
posision =set()
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision.add((h,w))
indx_H = [k for k,v in bom_H.items() if v == max(bom_H.values())]
indx_W = [k for k,v in bom_W.items() if v == max(bom_W.values())]
set_max_H = set(indx_H)
set_max_W = set(indx_W)
temp_H =max(bom_H.values())
temp_W =max(bom_W.values())

flag =False
for h in set_max_H:
    for w in set_max_W:
        if (h,w) not in posision:
            flag =True
            break
    if flag==True:
        break

if flag ==True:
    print(temp_H +temp_W )
else:
    print(temp_H +temp_W -1)

Submission status: Time Limit Exceeded

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

bom_H =defaultdict(int)
bom_W =defaultdict(int)
posision =set()
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision.add((h,w))
indx_H = [k for k,v in bom_H.items() if v == max(bom_H.values())]
indx_W = [k for k,v in bom_W.items() if v == max(bom_W.values())]
set_max_H = set(indx_H)
set_max_W = set(indx_W)
temp_H =max(bom_H.values())
temp_W =max(bom_W.values())

flag =False
for h in set_max_H:
    for w in set_max_W:
        if (h,w) not in posision:
            flag =True
            break

if flag ==True:
    print(temp_H +temp_W )
else:
    print(temp_H +temp_W -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, M = map(int, input().split())
lis =[]
Hlis = [0]*H
Wlis = [0]*W
for _ in range(M):
    Ch, Cm = map(int, input().split())
    Hlis[Ch-1] += 1
    Wlis[Cm-1] += 1
    lis.append([Ch, Cm])

Hmax = max(Hlis)
Hidx = [i+1 for i, v in enumerate(Hlis) if v == Hmax]
Wmax = max(Wlis)
Widx = [i+1 for i, v in enumerate(Wlis) if v == Wmax]

lis=tuple(lis)

for i in range(len(Hidx)):
    for j in range(len(Widx)):
        if [Hidx[i], Widx[j]] not in lis:
            print(Hmax+Wmax)
            sys.exit()
else:
    print(Hmax + Wmax -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
s = [[False]*w for _ in range(h)]

for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    s[a-1][b-1] = True
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
for i in yl:
    fl = False
    for j in xl:
        if not s[i][j]:
            res += 1
            fl = True
            break
    if fl: break
print(res)

Submission status: Time Limit Exceeded

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

ans = 0
max = 0

for x in h:
    for y in w:
        ans = h[x] + w[y]
        if [x, y] in bombs:
            ans -= 1
        if ans > max:
            max = ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = defaultdict(int)
xd = defaultdict(int)
s = [[False]*w for _ in range(h)]
for _ in range(m):
    a,b = inpl()
    yd[a-1] += 1
    xd[b-1] += 1
    s[a-1][b-1] = True
res = 0
for i in range(h):
    for j in range(w):
        tmp = 1 if s[i][j] else 0
        res = max(res, yd[i]+xd[j]-tmp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
h_list = [0] * h
w_list = [0] * w
bomb = []
for i in range(m):
    h_tmp, w_tmp = map(int, input().split())
    h_list[h_tmp - 1] += 1
    w_list[w_tmp - 1] += 1
    bomb.append((h_tmp - 1, w_tmp - 1))
mh = max(h_list)
id_h = []
for i, n in enumerate(h_list):
    if n == mh:
        id_h.append(i)

mw = max(w_list)
id_w = []
for i, n in enumerate(w_list):
    if n == mw:
        id_w.append(i)

for i in id_h:
    for j in id_w:
        if not (i, j) in bomb:
            print(mh + mw)
            exit()

print(mh + mw - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
for i in range(len(object)):
   if object[i][0] in cand_h and object[i][1] in cand_w:
      c += 1
print(ans - (c == p))

Submission status: Time Limit Exceeded

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

h, w, m = map(int, input().split())
col = [0]*w
row = [0]*h
ypos = []
xpos = []
bomb = []

for i in range(m):
    H, W = map(lambda x: int(x) - 1, input().split())
    col[W] += 1
    row[H] += 1
    bomb.append((H, W))

maxcol = max(col)
maxrow = max(row)

xpos = [h for h, x in enumerate(col) if x == maxcol]
ypos = [w for w, y in enumerate(row) if y == maxrow]

ans = maxcol + maxrow - 1

for i in ypos:
    for j in xpos:
        if (i, j) not in bomb:
            ans += 1
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


HH, WW, M = ints()
H, W = read_col(M)


def flatten(i, j): return i * WW + j


def reshape(x): return x // WW, x % WW


H = mina(*H)
W = mina(*W)
H_cnt = Counter(H)
W_cnt = Counter(W)
# 爆弾がある座標に関しては-1,それ以外はそのまま
# 爆弾のある座標の具体的な爆破数を持っていれば良い


def default_num(x):
    i, j = reshape(x)
    return H_cnt[i], W_cnt[j]


n_bomb = defaultdict(lambda: 0)
ma = -1
for h, w in zip(H, W):
    n_bomb[flatten(h, w)] = H_cnt[h] + W_cnt[w] - 1
    ma = max(ma, H_cnt[h] + W_cnt[w] - 1)

# 縦横大きい方から見てく
H_rank = H_cnt.most_common()
W_rank = W_cnt.most_common()
# print(H_rank, W_rank)

for i, h_cnt in H_rank:
    for j, w_cnt in W_rank:
        if h_cnt + w_cnt < ma:
            break  # どうあがいてもこれ以上大きくするのは無理
        n = n_bomb[flatten(i, j)]
        if n == 0:
            n = h_cnt + w_cnt
        ma = max(ma, n)

print(ma)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bom = [list(map(int, input().split())) for _ in range(M)]

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in bom:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if [h+1, w+1] not in bom:
            print(maxHBom + maxWBom)
            exit()
else:
    print(maxHBom + maxWBom - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bom = [list(map(int, input().split())) for _ in range(M)]

hBom = [0]*H
wBom = [0]*W

# 各行、各列の爆破対象をカウント
for h, w in bom:
    hBom[h-1] += 1
    wBom[w-1] += 1

# 爆破対象の最大数と最大になる行と列の番号を調べる
maxHBom = max(hBom)
maxWBom = max(wBom)
maxHBomIndex = [index for index, h in enumerate(hBom) if h == maxHBom]
maxWBomIndex = [index for index, w in enumerate(wBom) if w == maxWBom]

# 爆破対象が最大になる行と列の組み合わせについて、
# 爆弾を配置する場所が爆破対象であるかないかで場合分け
for h in maxHBomIndex:
    for w in maxWBomIndex:
        if [h+1, w+1] not in bom:
            print(hBom[h] + wBom[w])
            exit()
else:
    print(hBom[h] + wBom[w] - 1)

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb[h][w] = 1
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

ans = 0
for r in r_check:
    for c in c_check:
        if bomb[r][c] == 1:
            ans = max(ans, row[r] + column[c] - 1)
        else:
            ans = max(ans, row[r] + column[c])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
    h, w = map(int, input().split())
    h -=1
    w -=1
    row[w] += 1
    col[h] += 1
    memo.append((h, w))

col_max = col.max()
row_max = row.max()

max_col_indexs = np.where(col == col_max)[0]
max_row_indexs = np.where(row == row_max)[0]

ans = col_max + row_max -1
for c in max_col_indexs:
    for r in max_row_indexs:
        if (c, r) not in memo:
            ans = ans = col_max + row_max
            break

print(int(ans))

Submission status: Time Limit Exceeded

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

bomb = []
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb.append([h, w])
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

ans = 0
for r in r_check:
    for c in c_check:
        if [r, c] in bomb:
            ans = max(ans, row[r] + column[c] - 1)
        else:
            ans = max(ans, row[r] + column[c])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
hlist=[0]*(h+1)
wlist=[0]*(w+1)
cnt=[]


for i in range(m):
  a,b=map(int,input().split())
  hlist[a]+=1
  wlist[b]+=1
  cnt.append([a,b])


hcnt,wcnt=max(hlist),max(wlist)


hhh=[i for i,v in enumerate(hlist) if v==hcnt]
www=[i for i,v in enumerate(wlist) if v==wcnt]


for i in hhh:
  for j in www:
    if [i,j] not in cnt:
      print(hcnt+wcnt)
      exit()


print(hcnt+wcnt-1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
table = [[0 for i in range(w)] for i in range(h)]
sum_rows = [0 for i in range(h)]
sum_cols = [0 for i in range(w)]
for i in range(m):
    h_, w_ = map(int, input().split())
    table[h_-1][w_-1] = 1
    sum_rows[h_-1] += 1
    sum_cols[w_-1] += 1

m_rows = [i for i, val in enumerate(sum_rows) if val == max(sum_rows)]
m_cols = [i for i, val in enumerate(sum_cols) if val == max(sum_cols)]
flag = 0
for i in m_rows:
    for j in m_cols:
        if table[i][j] == 0:
            flag = 1
if flag:
    print(max(sum_cols)+max(sum_rows))
else:
    print(max(sum_cols)+max(sum_rows)-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
hlist=[0]*(h+1)
wlist=[0]*(w+1)
cnt=[]


for i in range(m):
  a,b=map(int,input().split())
  hlist[a]+=1
  wlist[b]+=1
  cnt.append([a,b])


hcnt,wcnt=max(hlist),max(wlist)

hh,ww=[],[]
hhh=[i for i,v in enumerate(hlist) if v==hcnt]
www=[i for i,v in enumerate(wlist) if v==wcnt]


for i in range(1,h+1):
  if hlist[i]==hcnt:
    hh+=[i]

for i in range(1,w+1):
  if wlist[i]==wcnt:
    ww+=[i]

for i in hh:
  for j in ww:
    if [i,j] not in cnt:
      print(hcnt+wcnt)
      exit()


print(hcnt+wcnt-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,m = map(int,input().split())
t = list(list(map(int,input().split())) for _ in range(m))

b = list([0]*w for _ in range(h))

for i in range(m):
  x,y = t[i]
  b[x-1][y-1] += 1

h_max = max(np.sum(b, axis=0))
w_max = max(np.sum(b, axis=1))

h_index = [n for n, v in enumerate(np.sum(b, axis=0)) if v == h_max]
w_index = [n for n, v in enumerate(np.sum(b, axis=1)) if v == w_max]

ans = h_max + w_max

for j in h_index:
  for k in w_index:
    if b[k][j] == 0:
      print(ans)
      exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h_list = [0 for _ in range(H + 1)]
w_list = [0 for _ in range(W + 1)]
bomb = []
for _ in range(M):
    h, w = map(int, input().split())
    h_list[h] += 1
    w_list[w] += 1
    bomb.append([h, w])
h_max = max(h_list)
w_max = max(w_list)
h_index = []
w_index = []
for i in range(H + 1):
    if h_list[i] == h_max:
        h_index.append(i)
for i in range(W + 1):
    if w_list[i] == w_max:
        w_index.append(i)
tmp = -1        
for h in h_index:
    for w in w_index:
        if [h, w] not in bomb:
            tmp = 0
            break
print(h_max + w_max + tmp)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
target_points = {tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)}

row_points = [0] * h
col_points = [0] * w
for row, col in target_points:
    row_points[row] += 1
    col_points[col] += 1

row_max = max(row_points)
col_max = max(col_points)

row_max_indexes = [i for i in range(h) if row_points[i] == row_max]
col_max_indexes = [i for i in range(w) if col_points[i] == col_max]

crossing_points = {(row, col) for row in row_max_indexes for col in col_max_indexes}

print(row_max + col_max - (not (crossing_points - target_points)))

Submission status: Time Limit Exceeded

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

h, w, m = map(int, input().split())
dpcol = [0]*w
dprow = [0]*h
ypos = []
xpos = []
hw = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]

for i, j in hw:
    dpcol[j] += 1
    dprow[i] += 1

maxcol = max(dpcol)
maxrow = max(dprow)

for i in range(w): #列の最大値
    if dpcol[i] == maxcol:
        xpos.append(i)

for i in range(h):
    if dprow[i] == maxrow:
        ypos.append(i)

ans = maxcol + maxrow - 1

for i in ypos:
    for j in xpos:
        if [i, j] not in hw:
            ans += 1
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
for _ in range(m):
    H, W = LI()
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1

m_h = max(cnt_h)
m_w = max(cnt_w)
H_l = []
W_l = []
for i in range(h):
    if cnt_h[i] == m_h:
        H_l.append(i)

for i in range(w):
    if cnt_w[i] == m_w:
        W_l.append(i)

ans = m_h + m_w

flag = False
for i in H_l:
    for j in W_l:
        if not bomb[(i, j)]:
            flag = True
if flag:
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
dpcol = [0]*w
dprow = [0]*h
ypos = []
xpos = []
hw = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]

for i, j in hw:
    dpcol[j] += 1
    dprow[i] += 1

maxcol = max(dpcol)
maxrow = max(dprow)

for i in range(w): #列の最大値
    if dpcol[i] == maxcol:
        xpos.append(i)

for i in range(h):
    if dprow[i] == maxrow:
        ypos.append(i)

for i in ypos:
    for j in xpos:
        if [i, j] in hw:
            ans = maxcol + maxrow - 1
        else:
            ans = maxcol + maxrow
            print(ans)
            exit()
print(ans)

Submission status: Time Limit Exceeded

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

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

ans =temp_H +temp_W -1
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==0:
            ans =v_h +v_w 
            print(ans)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]
hlist = [0]*(h+1)
wlist = [0]*(w+1)
for x,y in hw:
    hlist[x]+=1
    wlist[y]+=1

hmax=max(hlist) 
h_index = [n for n, v in enumerate(hlist) if v == hmax]
wmax=max(wlist)
w_index = [n for n, v in enumerate(wlist) if v == wmax]

count = sum(x in h_index and y in w_index for x,y in hw)
print(hmax+wmax-(len(h_index)*len(w_index)==count))

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
dpcol = [0]*w
dprow = [0]*h
ypos = []
xpos = []
anscol = 0
ansrow = 0
ans = 0
hw = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]

for i, j in hw:
    dpcol[j] += 1
    dprow[i] += 1

for i in range(w): #列の最大値
    if dpcol[i] > anscol:
        anscol = dpcol[i]
        xpos = [i]
    elif dpcol[i] == anscol:
        xpos.append(i)

for i in range(h):
    if dprow[i] > ansrow:
        ansrow = dprow[i]
        ypos = [i]
    elif dprow[i] == ansrow:
        ypos.append(i)

for i in ypos:
    for j in xpos:
        if [i, j] in hw:
            ans = anscol + ansrow - 1
        else:
            ans = anscol + ansrow
            print(ans)
            exit()
print(ans)