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: Accepted

Solution code:
def main():
    h, w, m = map(int, input().split())
    bombs_h = [0] * h
    bombs_w = [0] * w
    B = []
    for n in range(m):
        h1, w1 = map(lambda x: int(x)-1, input().split())
        B.append((h1, w1))
        bombs_w[w1] += 1
        bombs_h[h1] += 1
    max_h = max(bombs_h)
    max_w = max(bombs_w)
    h_maxindex = [i for i, x in enumerate(bombs_h) if x == max_h]
    w_maxindex = [i for i, x in enumerate(bombs_w) if x == max_w]
    cnt = 0
    k = len(h_maxindex) * len(w_maxindex)
    for i, j in B:
        if bombs_h[i] == max_h and bombs_w[j] == max_w:
            cnt += 1
    ans = max_h + max_w - (cnt == k)
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
x=[0]*h
y=[0]*w
c=[]
for _ in range(m):
  a,b=map(int,input().split())
  x[a-1]+=1
  y[b-1]+=1
  c+=[(a-1,b-1)]
mx=max(x)
my=max(y)
cnt=0
for i,j in c:
  if x[i]==mx and y[j]==my:cnt+=1
print(mx+my-(cnt==x.count(mx)*y.count(my)))

Submission status: Accepted

Solution code:
# 入力高速化
import sys
input = lambda: sys.stdin.readline().rstrip()

# 入力 (0-indexedにしつつ)
h, w, m = map(int, input().split())
hw = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

# 行/列 で爆破対象の出現回数をカウント
hcount = [0] * h
wcount = [0] * w
for a, b in hw:
  hcount[a] += 1
  wcount[b] += 1

# 出現回数の最大値を求める
hmax = max(hcount)
wmax = max(wcount)

# 爆弾を置く場所の候補数
x = hcount.count(hmax) * wcount.count(wmax)

# 爆破対象を見ていって、そこが爆弾を置く候補だったらxを-1
for a, b in hw:
  if hcount[a] == hmax and wcount[b] == wmax:
    x -= 1

# x=0になるということは、爆破できる対象がhmax+wmaxになる位置が存在しないということ
# 爆弾を置く候補すべてに既に爆破対象が置かれている
if x == 0:
  print(hmax + wmax - 1)
else:
  print(hmax + wmax)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

hw = []
hcount = [0] * h
wcount = [0] * w
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  hcount[a] += 1
  wcount[b] += 1
  hw.append([a, b])

hmax = max(hcount)
wmax = max(wcount)

x = hcount.count(hmax) * wcount.count(wmax)
for a, b in hw:
  if hcount[a] == hmax and wcount[b] == wmax:
    x -= 1

if x == 0:
  print(hmax + wmax - 1)
else:
  print(hmax + wmax)

Submission status: Accepted

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

bom = set()
for i in range(m):
    x,y = map(int,input().split())
    x-=1
    y-=1
    hb[x][0] += 1
    wb[y][0] += 1
    bom.add(tuple([x,y]))

ans = 0
hb.sort(reverse=True)
wb.sort(reverse=True)

for i,x in hb:
    for j,y in wb:
        a = i+j
        if (x,y) in bom:
            a -= 1
        if ans<a:
            ans = a
        else:
            break

for j,y in wb:
    for i,x in hb:
        a = i+j
        if (x,y) in bom:
            a -= 1
        if ans<a:
            ans = a
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n, p,q,r = map(int, input().split())
#arr = list(map(int, input().split()))
#n=int(input())
#n,m,k = map(int, input().split())
#n, m, k = [int(x) for x in input().split()]
#for _ in range(int(input())):
#n=int(input())
#arr = list(map(int, input().split()))
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_filled = 0
if len(row_max_indexes) * len(col_max_indexes) <= m:
    if all([(row, col) in target_points for row in row_max_indexes for col in col_max_indexes]):
        crossing_filled=1

print(row_max + col_max - crossing_filled)

Submission status: Accepted

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

target_pos = set()
target_n_row = [0] * h
target_n_col = [0] * w
for i in range(m):
    y, x = map(lambda x: int(x) - 1, input().split())
    target_n_row[y] += 1
    target_n_col[x] += 1
    target_pos.add((y, x))

sorted_row = [(a, i) for i, a in enumerate(target_n_row)]
sorted_row.sort(reverse=True)
sorted_col = [(a, i) for i, a in enumerate(target_n_col)]
sorted_col.sort(reverse=True)

max_r = sorted_row[0][0]
max_c = sorted_col[0][0]

i = 0
max_val = max_r + max_c - 1
while i < h and sorted_row[i][0] == max_r:
    j = 0
    while j < w and sorted_col[j][0] == max_c:
        if not (sorted_row[i][1], sorted_col[j][1]) in target_pos:
            max_val = sorted_row[i][0] + sorted_col[j][0]
            break
        j += 1
    i += 1
print(max_val)

Submission status: Accepted

Solution code:
from collections import defaultdict
def resolve():
    H,W,M = map(int,input().split())
    xc = defaultdict(int)
    yc = defaultdict(int)
    pos = set()

    for i in range(M):
        h,w = map(int,input().split())
        xc[w]+=1
        yc[h]+=1
        pos.add((h,w))
    xmax = max(xc.values())
    ymax = max(yc.values())
    xk = [k for k,v in xc.items() if v == xmax]
    yk = [k for k,v in yc.items() if v == ymax]
    for i in yk:
        for j in xk:
            if not (i,j) in pos:
                print(xmax+ymax)
                return
    print(xmax+ymax-1)
resolve()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
bombs_h = [0] * H
bombs_w = [0] * W
B = []
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    B.append((h, 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]
k = len(hs)*len(ws)
cnt = 0
for h, w in B:
    if bombs_h[h] == max_h and bombs_w[w] == max_w:
        cnt += 1
ans = max_w + max_h - (cnt == k)
print(ans)

Submission status: Accepted

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)
#存在チェックのアクセスがリストで持たせるより高速
#リストは突っ込めないので注意(hashabeのみOK)
bomb=set()
#O(H)
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add((hi,wi))

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

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

#O(H**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: Accepted

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

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

hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=set()
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add((hi,wi))

hmax=max(hcnt.values())
wmax=max(wcnt.values())

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

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: Accepted

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

HL, WL = [0]*H, [0]*W
B = []

for _ in range(M):
  h, w = map(lambda x:int(x)-1, input().split())
  B.append((h, w))
  HL[h] += 1
  WL[w] += 1

HM, WM = max(HL), max(WL)
K = HL.count(HM) * WL.count(WM)

cnt = 0
for h, w in B:
  if HL[h] == HM and WL[w] == WM:
    cnt += 1

if K > cnt:
  print(HM+WM)
else:
  print(HM+WM-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
R=[list(map(int,input().split())) for i in range(M)]
import sys
listH=[]
for i in range(H):
  listH.append(0)
for i in range(M):
  listH[R[i][0]-1]+=1
maxH=0
listHmax=[]
jH=0
for i in range(H):
  if listH[i]>maxH:
    maxH=listH[i]
    listHmax=[]
    listHmax.append(i)
    jH=1
  elif listH[i]==maxH:
    listHmax.append(i)
    jH+=1

listW=[]
for i in range(W):
  listW.append(0)
for i in range(M):
  listW[R[i][1]-1]+=1
maxW=0
listWmax=[]
jW=0
for i in range(W):
  if listW[i]>maxW:
    maxW=listW[i]
    listWmax=[]
    listWmax.append(i)
    jW=1
  elif listW[i]==maxW:
    listWmax.append(i)
    jW+=1

T=0
for i in range(M):
  if (listH[R[i][0]-1]==maxH and listW[R[i][1]-1]==maxW):
    T+=1
  else:
    continue
if T==jH*jW:
  print (maxH+maxW-1)
else:
  print (maxH+maxW)

Submission status: Accepted

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

target = set()
for _ in range(M):
    # h行, w列に爆破対象がある
    h, w = map(lambda x: int(x)-1, input().split())
    row[h] += 1
    column[w] += 1
    target.add((h, w))

max_row_value = max(row)
max_column_value = max(column)
max_row_idx = []
max_column_idx = []

for i in range(H):
    if row[i] == max_row_value:
        max_row_idx.append(i)
for j in range(W):
    if column[j] == max_column_value:
        max_column_idx.append(j)

# なければ出力して即終了
# print(max_row_idx)
# print(max_column_idx)
# print(target)
for r in max_row_idx:
    for c in max_column_idx:
        if (r, c) not in target:
            # この式がFalseになるのは，(r, c)に爆発対象があるときのみ，それはたかだか10**5回程度
            # 必ず上記の条件式がTrueになるときがくる
            # (r, c) in targetがTrueになるのは10**5回程度なので！
            print(max_row_value+max_column_value)
            exit()

print(max_row_value+max_column_value-1)

Submission status: Accepted

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
            break
    if flag:
        break

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

Submission status: Accepted

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)

for i in mh:
    for j in mw:
        if dic[(i, j)] == 0:
            print(max_h + max_w)
            quit()

print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


H,W,M = input().rstrip().split(' ')

H = int(H)
W = int(W)
M = int(M)

hcount = [0 for _ in range(H)]
wcount = [0 for _ in range(W)]

#L = [[0 for i in range(W)]for j in range(H)]
L = {}
for i in range(M):
    ij = input().rstrip().split(' ')
    i = int(ij[0])-1
    j = int(ij[1])-1
    #L[i][j] = 1
    L[(i,j)] = 1
    hcount[i] += 1
    wcount[j] += 1
 
hmax = max(hcount)
wmax = max(wcount)
count = hmax+wmax-1

hin = [i for i, x in enumerate(hcount) if x == hmax]
win = [i for i, x in enumerate(wcount) if x == wmax]

for i in hin:
    for j in win:
      if (i, j) not in L:
            count = hmax+wmax
            break
print(count)

Submission status: Accepted

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))
temp_H =max(bom_H.values())
temp_W =max(bom_W.values())
indx_H = [k for k,v in bom_H.items() if v == temp_H]
indx_W = [k for k,v in bom_W.items() if v == temp_W]
set_max_H = set(indx_H)
set_max_W = set(indx_W)


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: Accepted

Solution code:
h, w, m = map(int, input().split())
hw = set()
hh = [0]*h
ww = [0]*w
for _ in range(m):
    h, w = map(int, input().split())
    h-=1
    w-=1
    hw.add(h*10**6+w)
    hh[h] += 1
    ww[w] += 1
mxh = max(hh)
mxw = max(ww)
mh = [i for i, j in enumerate(hh) if j==mxh]
mw = [i for i, j in enumerate(ww) if j==mxw]
for i in mh:
    for j in mw:
        if i*10**6+j not in hw:
            print(mxh+mxw)
            exit(0)
print(mxh+mxw-1)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, input().split())
Hb = [0] * H
Wb = [0] * W
B = set()
for _ in range(M):
    h, w = map(int, input().split())
    Hb[h - 1] += 1
    Wb[w - 1] += 1
    B.add((h - 1, w - 1))
HB = max(Hb)
WB = max(Wb)
x = set()
y = set()
for i in range(H):
    if Hb[i] == HB:
        y.add(i)
for i in range(W):
    if Wb[i] == WB:
        x.add(i)
for i in y:
    for j in x:
        if (i, j) not in B:
            print(HB + WB)
            sys.exit()
print(HB + WB - 1)

Submission status: Accepted

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

cache = set()
for _ in range(M):
    h, w = map(int, input().split())
    HC.update([h])
    WC.update([w])
    cache.add((h, w))

HCS = sorted(HC.items(), key=lambda x: x[1],reverse=True)
WCS = sorted(WC.items(), key=lambda x: x[1],reverse=True)

hmax = HCS[0][1]
hmaxkeys = [HCS[0][0]]
for hi in range(1, len(HCS)):
    if HCS[hi][1] == hmax:
        hmaxkeys.append(HCS[hi][0])
    else:
        break

wmax = WCS[0][1]
wmaxkeys = [WCS[0][0]]
for wi in range(1, len(WCS)):
    if WCS[wi][1] == wmax:
        wmaxkeys.append(WCS[wi][0])
    else:
        break

for hi in hmaxkeys:
    for wi in wmaxkeys:
        if not (hi, wi) in cache:
            print(hmax + wmax)
            exit(0)

print(hmax + wmax - 1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
dicti={}
dictj={}
bomb=set()
for i in range(M):
  h,w=map(int,input().split())
  bomb.add((h,w))
  if h in dicti:
    dicti[h]+=1
  if h not in dicti:
    dicti[h]=1
  if w in dictj:
    dictj[w]+=1
  if w not in dictj:
    dictj[w]=1
LI=sorted(dicti.items(),key=lambda x:x[1],reverse=True)
LJ=sorted(dictj.items(),key=lambda x:x[1],reverse=True)
Imax=LI[0][1]
Jmax=LJ[0][1]
I=0
J=0
IL=[]
JL=[]
for i in range(len(LI)):
  if LI[i][1]==Imax:
    IL.append(LI[i][0])
for i in range(len(LJ)):
  if LJ[i][1]==Jmax:
    JL.append(LJ[i][0])
  
ans=Imax+Jmax-1

for h in IL:
  for w in JL:
    if (h,w) not in bomb:
      ans=Imax+Jmax
      break
print(ans)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, input().split())
lis =set()
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.add((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]

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: Accepted

Solution code:
h,w,m = map(int, input().split())
bomb=[list(map(int,input().split())) for i in range(m)]
cnt_h=[0]*h
cnt_w=[0]*w

for h,w in bomb:
    cnt_h[h-1]+=1
    cnt_w[w-1]+=1

mx_h=max(cnt_h)
mx_w=max(cnt_w)
mxh_ind=cnt_h.count(mx_h)
mxw_ind=cnt_w.count(mx_w)

hit=0
for h,w in bomb:
    if cnt_h[h-1]==mx_h and cnt_w[w-1]==mx_w:
        hit+=1

if hit==mxh_ind*mxw_ind:
    print(mx_h+mx_w-1)
else:
    print(mx_h+mx_w)

Submission status: Accepted

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
YX = [tuple(map(int, input().split())) for i in range(M)]
yx_set = set(YX)

xc = Counter()
yc = Counter()

for y, x in YX:
    yc[y] += 1
    xc[x] += 1

ans = 0
for y, x in YX:
    ans = max(ans, yc[y] + xc[x] - 1)

xmc = xc.most_common()
ymc = yc.most_common()
xmx = xmc[0][1]
ymx = ymc[0][1]
for xk, xv in xmc:
    if xv < xmx:
        break
    for yk, yv in ymc:
        if yv < ymx:
            break
        if (yk, xk) in yx_set:
            continue
        ans = max(ans, yv + xv)
        break
print(ans)

Submission status: Accepted

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

hs=[0]*H
ws=[0]*W
D=defaultdict(int)
for i in range(M):
    h,w=map(int, input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    D[(h-1,w-1)]+=1


hmax=max(hs)
wmax=max(ws)
Hs=[]
Ws=[]
for h in range(H):
    if hmax==hs[h]:
        Hs.append(h)

for w in range(W):
    if wmax==ws[w]:
        Ws.append(w)

for h in Hs:
    for w in Ws:
        if D[h,w]==0:
            print(hmax+wmax)
            exit()

print(hmax+wmax-1)

Submission status: Accepted

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

p=max(H)
q=max(W)

X=set([i for i in range(3*10**5+1) if H[i]==p])
Y=set([i for i in range(3*10**5+1) if W[i]==q])

cnt=0
for i in range(m):
    if M[i][0] in X and M[i][1] in Y:
        cnt+=1

if cnt==len(X)*len(Y):
    print(p+q-1)
else:
    print(p+q)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

row_dict = defaultdict(int)
col_dict = defaultdict(int)
row_col_dict = defaultdict(set)
for _ in range(m):
    row, col = map(int, input().split())
    row_dict[row] += 1
    col_dict[col] += 1
    row_col_dict[row].add(col)

max_row = max(row_dict.values())
max_col = max(col_dict.values())

max_rows = {k for k, v in row_dict.items() if v == max_row}
max_cols = {k for k, v in col_dict.items() if v == max_col}
ans = max_row + max_col - 1
flg = False
if ans < m:
    for row in max_rows:
        for col in max_cols:
            if not col in row_col_dict[row]:
                ans += 1
                flg = True
                break
        if flg:
            break

print(ans)

Submission status: Accepted

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_filled = len(row_max_indexes) * len(col_max_indexes) <= m and \
                  all([(row, col) in target_points for row in row_max_indexes for col in col_max_indexes])

print(row_max + col_max - crossing_filled)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w,m=map(int,input().split())
l={}
u={}
hw=[list(map(int,input().split())) for _ in range(m)]
s=set()

for i in range(m):
    hr,wr=hw[i]
    if hr-1 in u:
        u[hr-1]+=1
    else:
        u[hr-1]=1
    if wr-1 in l:
        l[wr-1]+=1
    else:
        l[wr-1]=1
    s.add((hr-1)*w+wr-1)
resl=0
resu=0
cl=[]
cu=[]
for i in l:
    if resl<l[i]:
        resl=l[i]
        cl=[i]
    elif resl==l[i]:
        cl.append(i)
for i in u:
    if resu<u[i]:
        resu=u[i]
        cu=[i]
    elif resu==u[i]:
        cu.append(i)
ans=0
if resu==m or resl==m :
  print(m)
  exit()
if len(cu)*len(cl)>m:
    ans=resl+resu
else:
    for i in cu:
        for j in cl:
            if i*w+j in s:
                res=resl+resu-1
            else:
                res=resl+resu
            ans=max(res,ans)
print(ans)

Submission status: Accepted

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

rows = [0] * H
cols = [0] * W
s = set()
for _ in range(M):
    h, w = map(lambda x: int(x) - 1,input().split())
    rows[h] += 1
    cols[w] += 1
    s.add((h, w))

max_rows = max(rows)
max_cols = max(cols)

max_rows_indexes = [i for i in range(H) if rows[i] == max_rows]
max_cols_indexes = [i for i in range(W) if cols[i] == max_cols]

duplicate = True
if M >= len(max_rows_indexes) * len(max_cols_indexes):
    for h in max_rows_indexes:
        for w in max_cols_indexes:
            if (h, w) not in s:
                duplicate = False
                break
        if not duplicate:
            break
else:
    duplicate = False

if duplicate:
    print(max_rows + max_cols - 1)
else:
    print(max_rows + max_cols)

Submission status: Accepted

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)
cand_h = set(cand_h)
cand_w = set(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: Accepted

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))
bomb = set(bomb)
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: Accepted

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

rows = [0] * H
cols = [0] * W
s = set()
for _ in range(M):
    h, w = map(lambda x: int(x) - 1,input().split())
    rows[h] += 1
    cols[w] += 1
    s.add((h, w))

max_rows = max(rows)
max_cols = max(cols)

result = max_rows + max_cols - 1
max_rows_indexes = [i for i in range(H) if rows[i] == max_rows]
max_cols_indexes = [i for i in range(W) if cols[i] == max_cols]
for h in max_rows_indexes:
    for w in max_cols_indexes:
        if (h, w) not in s:
            result = max_rows + max_cols
            break
print(result)

Submission status: Accepted

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

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

# 各行、各列の爆破対象をカウント
for h, w in boms:
    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]

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

Submission status: Accepted

Solution code:

def resolve():
    H, W, M = map(int, input().split())
    XY = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

    X = [0] * H  # X:各行の爆破対象の個数
    Y = [0] * W  # Y:各列の爆破対象の個数
    for h, w in XY:
        X[h] += 1
        Y[w] += 1
    maxX = max(X)
    maxY = max(Y)

    R = [i for i, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
    C = [i for i, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

    bomb = set(XY)
    for r in R:
        for c in C:
            # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため,
            # 即座に探索を終了する.
            if (r, c) not in bomb:
                print(maxX + maxY)
                return
    # 座標(A,B)に爆発対象が存在した場合重複し、RAにもCBにも値が 1 足されてしまう。
    # 実際の爆発対象は 1 つしかないため、実際に爆発する爆発対象の個数は RA+CB−1 となる
    print(maxX + maxY - 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
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)

for i in range(w):
    if col[i] == maxcol:
        xpos.append(i)
for i in range(h):
    if row[i] == maxrow:
        ypos.append(i)

ans = maxcol + maxrow - 1
bomb = set(bomb) #setにすると速い

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

Submission status: Accepted

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

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

Submission status: Accepted

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,それ以外はそのまま
# 爆弾のある座標の具体的な爆破数を持っていれば良い


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: Accepted

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_indexes = np.where(col == col_max)[0]
max_row_indexes = np.where(row == row_max)[0]

ans = col_max + row_max -1
memo = set(memo)
for c in max_col_indexes:
    for r in max_row_indexes:
        if (c, r) not in memo:
            ans = ans = col_max + row_max
            print(int(ans))
            exit()

print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter
H,W,m = map(int,input().split())
ci = Counter([])
cj = Counter([])
s = set()
for i in range(m):
    h,w = map(int,input().split())
    ci[h] += 1
    cj[w] += 1
    s.add((h,w))
mi = max(ci.values())
mj = max(cj.values())
ci = list(ci.items())
cj = list(cj.items())
xi = [ci[i][0] for i in range(len(ci)) if ci[i][1] == mi]
xj = [cj[i][0] for i in range(len(cj)) if cj[i][1] == mj]
for i in xi:
    for j in xj:
        if (i,j) not in s:
            print(mi+mj)
            quit()
print(mi+mj-1)

Submission status: Accepted

Solution code:
import numpy as np
def main():
    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
    memo = set(memo)
    for c in max_col_indexs:
        for r in max_row_indexs:
            if (c, r) not in memo:
                ans = ans = col_max + row_max
                print(int(ans))
                exit()

    print(int(ans))

if __name__ == "__main__":
    main()