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:
H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W

L = []

for _ in range(M):
    h, w = map(int,input().split())
    R[h-1] += 1
    C[w-1] += 1
    L.append([h-1, w-1])

r = max(R)
c = max(C)

print(r + c - (R.count(r) * C.count(c) == sum(R[h] + C[w] == r + c for h, w in L)))

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, input().split())
hn = [0]*H
wn = [0]*W
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  hn[h-1] += 1
  wn[w-1] += 1
  flag.add((h,w))
  
#hrank = sorted(hn, key=lambda t:-t[1])
#wrank = sorted(wn, key=lambda t:-t[1])

hmax = max(hn)
wmax = max(wn)

hmaxlist = {i+1 for i,h in enumerate(hn) if h == hmax}
#for h in hn:
#  if h == hmax:
#    hmaxlist.append(h)
  
wmaxlist = {i+1 for i,w in enumerate(wn) if w == wmax}
#for w in wn:
#  if w == wmax:
#    wmaxlist.append(w)
  

for i in hmaxlist:
  for j in wmaxlist:
    if (i,j) not in flag:
      print(hmax+wmax)
      sys.exit()
print(hmax+wmax-1)

Submission status: Accepted

Solution code:
import sys

H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W

S = set()

for _ in range(M):
    h, w = map(int,input().split())
    S.add((h-1, w-1))
    R[h-1] += 1
    C[w-1] += 1

r = max(R)
c = max(C)

HL = [i for i in range(H) if R[i] == r]
WL = [i for i in range(W) if C[i] == c]

for h in HL:
    for w in WL:
        if not (h, w) in S:
            print(r + c)
            sys.exit()

print(r + c - 1)

Submission status: Accepted

Solution code:
import sys

H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W
S = set()
for _ in range(M):
    h, w = map(int,input().split())
    S.add((h-1, w-1))
    R[h-1] += 1
    C[w-1] += 1

r = max(R)
c = max(C)

HL = [i for i in range(H) if R[i] == r]
WL = [i for i in range(W) if C[i] == c]

for h in HL:
    for w in WL:
        if not (h, w) in S:
            print(r + c)
            sys.exit()

print(r + c - 1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
A=[0]*h ; B=[0]*w ;G=[]
for i in range(m):
    x,y=map(int,input().split())
    A[x-1]+=1 ; B[y-1]+=1
    G.append([x-1,y-1])

q=max(A) ; e=max(B)
Q=[i for i in range(h) if A[i]==q] 
W=[j for j in range(w) if B[j]==e];#print(A,B,Q,W)
cnt=len(Q)*len(W)



for i in range(m):
    x,y=G[i]
    if A[x]==q and B[y]==e:
        cnt-=1
#print(grid)
if cnt==0:
    print(q+e-1)
else:
    print(q+e)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
bombX = [0]*h
bombY = [0]*w
bomb = set()
maxX = maxY = 0
for i in range(m):
    i,j = map(lambda x:int(x)-1, input().split())
    bomb.add((i,j))
    bombX[i] += 1
    bombY[j] += 1
    maxX = max(maxX,bombX[i])
    maxY = max(maxY,bombY[j])
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) in bomb: continue
        print(maxX+maxY)
        exit()
print(maxX+maxY-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
X = [0 for i in range(H)]
Y = [0 for j in range(W)]
s = set([])
for i in range(M):
  h, w = map(int, input().split())
  X[h-1] += 1
  Y[w-1] += 1
  s.add((h-1, w-1)) #タプルを使う
mX = max(X)
mY = max(Y)
I = [i for i in range(H) if X[i] == mX]
J = [j for j in range(W) if Y[j] == mY]
flag = 0
for i in I:
  for j in J:
    if {(i, j)} <= s:
      continue
    flag = 1
    print(mX+mY)
    break
  if flag == 1:
    break
if flag == 0:
  print(mX+mY-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]
Tr=[0 for _ in range(H+1)]
Tc=[0 for _ in range(W+1)]
for i in range(M):
    Tr[s[i][0]]+=1
    Tc[s[i][1]]+=1
mr=max(Tr)
mc=max(Tc)
Mr=[0 for _ in range(H+1)]
Mc=[0 for _ in range(W+1)]
Nmr=0
Nmc=0
for i in range(len(Tr)):
    if Tr[i]==mr:
        Mr[i]=1
        Nmr+=1
for i in range(len(Tc)):
    if Tc[i]==mc:
        Mc[i]=1
        Nmc+=1
cnt=0
for i in range(M):
    if Mr[s[i][0]]==1 and Mc[s[i][1]]==1:
        cnt+=1
if cnt<Nmr*Nmc:
    print(mr+mc)
else:
    print(mr+mc-1)

Submission status: Accepted

Solution code:
x, y, m = map(int,input().split())
mat = set()
r = [0]*x
c = [0]*y
smx = 0
smy = 0
for _ in range(m):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    mat.add((p,q))
    r[p] += 1
    c[q] += 1
    smx = max(smx,r[p])
    smy = max(smy,c[q])
xs = []
ys = []
for i in range(x):
    if smx == r[i]: xs.append(i)
for i in range(y):
    if smy == c[i]: ys.append(i)

ans = smx + smy - 1

for h in xs:
    for w in ys:
        if (h, w) in mat: continue
        print(ans + 1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
def solve(h, w, m, hw_list):
    h_count = [0] * (h + 1)
    w_count = [0] * (w + 1)
    for h_, w_ in hw_list:
        h_count[h_] += 1
        w_count[w_] += 1

    h_max = max(h_count)
    w_max = max(w_count)
    res = h_max + w_max

    h_max_count = 0
    w_max_count = 0
    for i in range(h + 1):
        if h_count[i] == h_max:
            h_max_count += 1
    for j in range(w + 1):
        if w_count[j] == w_max:
            w_max_count += 1

    max_count = h_max_count * w_max_count
    max_count_cross = 0
    for h_, w_ in hw_list:
        if h_count[h_] == h_max and w_count[w_] == w_max:
            max_count_cross += 1

    if max_count_cross == max_count:
        return res - 1
    else:
        return res


def main():
    h, w, m = map(int, input().split())
    hw_list = []
    for _ in range(m):
        hw_list.append(list(map(int, input().split())))
    res = solve(h, w, m, hw_list)
    print(res)


def test():
    assert solve(2, 3, 3, [[2, 2], [1, 1], [1, 3]]) == 3
    assert solve(3, 3, 4, [[3, 3], [3, 1], [1, 1], [1, 2]]) == 3
    assert solve(5, 5, 10, [[2, 5], [4, 3], [2, 3], [5, 5], [2, 2], [5, 4], [5, 3], [5, 1], [3, 5], [1, 4]]) == 6


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

H,W=[0]*h,[0]*w
for i,j in HW:
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i]==max_h and W[j]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = max(hc)
    maw = max(wc)
    ans = mah+maw
    hmaps = []
    wmaps = []
    for i, h in enumerate(hc):
        if mah == h:
            hmaps.append(i)
    for i, w in enumerate(wc):
        if maw == w:
            wmaps.append(i)

    if M < len(hmaps) * len(wmaps):
        # 爆破対象の合計が最大になるマスがM個より多ければ，
        # 必ず爆破対象がないマスに爆弾を置くことができる
        # 逆にM個以下なら3*10^5のループにしかならないので
        # このようにif文で分けなくても，必ずO(M)になるのでelse節のforを回してよい
        print(ans)
    else:
        for h in hmaps:
            for w in wmaps:
                if (h, w) not in maps:
                    print(ans)
                    return
        else:
            print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = -1
    maw = -1
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah < h:
            mah = h
            hmaps = {i}
        elif mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw < w:
            maw = w
            wmaps = {i}
        elif maw == w:
            wmaps.add(i)
    ans = mah+maw
    aru = True

    for h in hmaps:
        for w in wmaps:
            if (h, w) not in maps:
                aru = False
                break
        if not aru:
            break
    if aru:
        print(ans - 1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = -1
    maw = -1
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah < h:
            mah = h
            hmaps = {i}
        elif mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw < w:
            maw = w
            wmaps = {i}
        elif maw == w:
            wmaps.add(i)
    ans = mah+maw

    for h in hmaps:
        for w in wmaps:
            if (h, w) not in maps:
                print(ans)
                return
    else:
        print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = max(hc)
    maw = max(wc)
    ans = mah+maw
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw == w:
            wmaps.add(i)

    for h in hmaps:
        for w in wmaps:
            if (h, w) not in maps:
                print(ans)
                return
    else:
        print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import pprint
H, W, M = map(int, input().split())
bombs = set()
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.add((h, w))

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

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

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = max(hc)
    maw = max(wc)
    ans = mah+maw
    hmaps = []
    wmaps = []
    for i, h in enumerate(hc):
        if mah == h:
            hmaps.append(i)
    for i, w in enumerate(wc):
        if maw == w:
            wmaps.append(i)

    for h in hmaps:
        for w in wmaps:
            if (h, w) not in maps:
                print(ans)
                return
    else:
        print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

HW = set()
sum_h = [0]*H; sum_w = [0]*W
max_sum_h = max_sum_w = 0
for _ in range(M):
    h, w = map(lambda x:int(x)-1, input().split())
    HW.add((h, w))
    sum_h[h] += 1
    sum_w[w] += 1
    max_sum_h = max(max_sum_h, sum_h[h])
    max_sum_w = max(max_sum_w, sum_w[w])

hs = []; ws = []
for i in range(H):
    if sum_h[i] == max_sum_h: hs.append(i)
for i in range(W):
    if sum_w[i] == max_sum_w: ws.append(i)

ans = max_sum_h + max_sum_w - 1
for h in hs:
    for w in ws:
        if (h, w) in HW: continue
        print(ans + 1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, M = (int(i) for i in input().split())
    hc = [0]*(H+1)
    wc = [0]*(W+1)
    maps = set()
    for _ in range(M):
        h, w = (int(i) for i in input().split())
        hc[h] += 1
        wc[w] += 1
        maps.add((h, w))
    mah = -1
    maw = -1
    hmaps = set()
    wmaps = set()
    for i, h in enumerate(hc):
        if mah < h:
            mah = h
            hmaps = {i}
        elif mah == h:
            hmaps.add(i)
    for i, w in enumerate(wc):
        if maw < w:
            maw = w
            wmaps = {i}
        elif maw == w:
            wmaps.add(i)
    ans = mah+maw
    aru = True
    if len(hmaps) * len(wmaps) <= 5*10**6:
        for h in list(hmaps):
            for w in list(wmaps):
                if (h, w) not in maps:
                    aru = False
                    break
    else:
        aru = False
    if aru:
        print(ans - 1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

bom = []
for i in range(M):
    h, w = map(int, input().split())
    bom.append([h, w])
    row[h] += 1
    col[w] += 1
 
rmax = max(row)
cmax = max(col)
cnt = row.count(rmax) * col.count(cmax)

for h, w in bom:
    if rmax == row[h] and cmax == col[w]:
        cnt -= 1

print(rmax + cmax - (cnt == 0))

Submission status: Accepted

Solution code:
R, C, T = map(int, input().split())
RC = []
for _ in range(T):
    RC.append(list(map(int, input().split())))
TR = [0] * (R + 1)
TC = [0] * (C + 1)
mxr=0
mxc=0
for r, c in RC:
    TR[r] += 1
    TC[c] += 1
    if(TR[r]>mxr):
      mxr=TR[r]
    if(TC[c]>mxc):
      mxc=TC[c]
ct = TR.count(mxr) * TC.count(mxc) - len([0 for r, c in RC if TR[r] == mxr and TC[c] == mxc])
print(mxc + mxr - (ct == 0))

Submission status: Accepted

Solution code:
R, C, T = map(int, input().split())
RC = []
for _ in range(T):
    RC.append(list(map(int, input().split())))
TR = [0] * (R + 1)
TC = [0] * (C + 1)
for r, c in RC:
    TR[r] += 1
    TC[c] += 1
mxr = max(TR)
mxc = max(TC)
ct = TR.count(mxr) * TC.count(mxc) - len([0 for r, c in RC if TR[r] == mxr and TC[c] == mxc])
print(mxc + mxr - (ct == 0))

Submission status: Accepted

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

num_h = [0] * (h+1)
num_w = [0] * (w+1)
bomb_set = set()
for hi,wi in bomb:
  num_h[hi] += 1
  num_w[wi] += 1
  bomb_set.add((hi,wi))
  
max_h = max(num_h)
max_w = max(num_w)
max_hs = [k for k,v in enumerate(num_h) if v == max_h]
max_ws = [k for k,v in enumerate(num_w) if v == max_w]

result = max_h + max_w
for i in max_hs:
  for j in max_ws:
    if (i,j) not in bomb_set:
      print(result)
      exit(0)
print(result-1)

Submission status: Accepted

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

A = [0] * (H + 1)
B = [0] * (W + 1)
for h, w in HW:
    A[h] += 1
    B[w] += 1

a = max(A)
b = max(B)

cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])

print(a + b - (cnt == 0))

Submission status: Accepted

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

for i in range(M):
    ARR.append(list(map(int,input().split())))

def calculate(h, w, m, arr):
    points = set()



    rowSum = [0 for i in range(h)]
    columnSum = [0 for i in range(w)]

    for ar in arr:
        points.add((ar[0]-1, ar[1]-1))
        rowSum[ar[0]-1] += 1
        columnSum[ar[1]-1] += 1

    maxRowSum = max(rowSum)
    maxColumnSum = max(columnSum)


    a0 = []

    for i in range(len(rowSum)):
        if rowSum[i] == maxRowSum:
            a0.append(i)

    a1 = []
    for i in range(len(columnSum)):
        if columnSum[i] == maxColumnSum:
            a1.append(i)

    result = 0
    for hIndex in a0:
        for wIndex in a1:

            if (hIndex,wIndex) in points:
                result = max(result, maxRowSum + maxColumnSum - 1)
            else:
                result = max(result, maxRowSum + maxColumnSum)
                print(result)
                exit()

    print(result)


calculate(H, W, M, ARR)

Submission status: Accepted

Solution code:
import collections
h, w, m = map(int, input().split())
h = [None]*m
w = [None]*m
for i in range(m):
    u, v = map(int, input().split())
    h[i] = u
    w[i] = v
hc = collections.Counter(h)
wc = collections.Counter(w)
hm = hc.most_common()[0][1]
hs = set([])
for hi, ci in hc.most_common():
    if ci == hm:
        hs.add(hi)
    else:
        break
wm = wc.most_common()[0][1]
ws = set([])
for wi, ci in wc.most_common():
    if ci == wm:
        ws.add(wi)
    else:
        break
cnt = 0
for i in range(m):
    if h[i] in hs and w[i] in ws:
        cnt += 1
if cnt == len(hs)*len(ws):
    print(hm + wm -1)
else:
    print(hm + wm)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
DP = set()
for i in range(M):
    hh, ww = map(int, input().split())
    h[hh - 1] += 1
    w[ww - 1] += 1
    DP.add((hh - 1, ww - 1))

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0

for i in hhhh:
    for j in wwww:
        if (i, j) not in DP:
            print(hhh + www)
            exit()
print(hhh + www - 1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
d_h=[0]*(h+1)
d_w=[0]*(w+1)
d=[]
for i in range(m):
  nh,nw=map(int,input().split())
  d_h[nh]+=1
  d_w[nw]+=1
  d.append([nh,nw])
  
#print(d_h)
#print(d_w)

hantei=0
ans1=max(d_h)
memoh=set()
for i in range(1,h+1):
  hantei=d_h[i]
  if ans1==hantei:
    memoh.add(i)
    
hantei=0
ans2=max(d_w)
memow=set()
for j in range(1,w+1):
  hantei=d_w[j]
  if ans2 == hantei:
    memow.add(j)
ans = ans2+ans1-1
#print(memoh,memow)
count = len(memoh)*len(memow)
for hw in d:
  if hw[0] in memoh and hw[1] in memow:
    count-=1
if count>0:
  print(ans+1)
else:
  print(ans)

Submission status: Accepted

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

    h_totals = [0] * (H+1)
    w_totals = [0] * (W+1)
    overlap = [set() for _ in range(H+1)]

    for ph, pw in pos:
        h_totals[ph] += 1
        w_totals[pw] += 1
        overlap[ph].add(pw)

    max_h = -1
    max_w = -1
    h_list = []
    w_list = []
    for i in range(1, H+1):
        if h_totals[i] > max_h:
            max_h = h_totals[i]
            h_list = [i]
        elif h_totals[i] == max_h:
            h_list.append(i)
    for j in range(1, W+1):
        if w_totals[j] > max_w:
            max_w = w_totals[j]
            w_list = [j]
        elif w_totals[j] == max_w:
            w_list.append(j)

    for i in h_list:
        for j in w_list:
            if j not in overlap[i]:
                print(max_h + max_w)
                return
    print(max_h + max_w - 1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def e_bomber():
    import sys
    input = sys.stdin.readline

    H, W, M = [int(i) for i in input().split()]

    bomb_row = [0] * H
    bomb_col = [0] * W
    bomb_pos = set()
    for _ in range(M):
        r, c = [int(i) - 1 for i in input().split()]
        bomb_row[r] += 1
        bomb_col[c] += 1
        bomb_pos.add((r, c))

    bomb_row_max = max(bomb_row)
    bomb_col_max = max(bomb_col)
    row_index_list = [r for r, v in enumerate(bomb_row) if v == bomb_row_max]
    col_index_list = [c for c, v in enumerate(bomb_col) if v == bomb_col_max]

    # 破壊できる数が最大になるような行と列の組を全探索する。
    # (行, 列) が破壊対象の上になってしまわないような組があれば、そこに置けばいい。
    # そのような組がまったくなければ、破壊対象の上に置かざるを得ない (-1 される)。
    for row in row_index_list:
        for col in col_index_list:
            if (row, col) not in bomb_pos:
                return bomb_row_max + bomb_col_max
    return bomb_row_max + bomb_col_max - 1

print(e_bomber())

Submission status: Accepted

Solution code:
from collections import defaultdict
h, w, m = map(int, input().split())
targets = []
targets_count_w = defaultdict(int)
targets_count_h = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_w[x] += 1
    targets_count_h[y] += 1
    targets.append((y, x))

max_w = max(targets_count_w.values())
max_h = max(targets_count_h.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_w[i] == max_w:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_h[i] == max_h:
        y_idx[i] = True
        max_count_y += 1


ans = max_w + max_h
kumi = max_count_x*max_count_y
for ty, tx in targets:
    if y_idx[ty] and x_idx[tx]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

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

#方針
# 1,基本的には、行和の最大と列和の最大の和が答えとなる
# 2,例外として、行和の最大を与える行と、列和の最大を与える列との交差点が、
#   全て爆破対象で埋まっている場合(飽和)、重複分の1を引く必要がある。

A = [0 for _ in range(H)] # 各行の爆破対象の個数 (行和)
B = [0 for _ in range(W)] # 各列の爆破対象の個数 (列和)
C = set() # 爆破対象の位置の集合

for _ in range(M): #入力処理
  h, w = map(int, input().split())
  A[h-1] += 1
  B[w-1] += 1
  C.add((h-1, w-1))

# 処理1, 行和の最大と列和の最大の和を求める
d = max(A) # 行和の最大
e = max(B) # 列和の最大
ans = d+e # 爆破できる最大の個数(仮)

# 処理2, 飽和を検出する
#  方針: 「交差点個数 == 交差点上の対象物個数」 なら飽和とする

F = set() # 最大を与える行の集合
G = set() # 最大を与える列の集合
for h in range(H):
  if A[h] == d:
    F.add(h)
for w in range(W):
  if B[w] == e:
    G.add(w)
  
spot = len(F)*len(G) # 最大を与える列と、最大を与える行の交差点の個数
bm_on_spot = 0 # 上記交差点の上にある対象物の個数 (以下のループ中でカウントする)
for c in C:
  if c[0] in F and c[1] in G: # 対象物が交差点上にある場合,カウント+1
    bm_on_spot += 1
    
if bm_on_spot == spot: #「交差点個数 == 交差点上の対象物個数」 なら飽和とする
  ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, M = map(int, input().split())
Bh = [0]*(H+1)
Bw = [0]*(W+1)
OD = set()

for _ in range(M):
    h, w = map(int, input().split())
    Bh[h] += 1
    Bw[w] += 1
    OD.add((h, w))

M1 = max(Bh)
M2 = max(Bw)
l1 = [i for i, x in enumerate(Bh) if x == M1]
l2 = [j for j, x in enumerate(Bw) if x == M2]
for i, j in itertools.product(l1, l2):
    if (i, j) not in OD:
        break
else:
    print(M1+M2-1)
    exit()
print(M1+M2)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
#二次元リストではなく列行を一個のボムで消してくれるためそれぞれのリストを用意。
sumh = [0] * H
sumw = [0] * W
bomb=[]

for i in range(M):
    h,w=map(int,input().split())
    sumh[h-1]+=1
    sumw[w-1]+=1
    bomb.append((h,w))

#爆弾の個数の最大値とその最大値がいくつずつあるか(ch,cw)に保存。最大の列と最大の行のいずれかの組み合わせに置くことで爆破数を最大化できる。
maxh=max(sumh)
maxw=max(sumw)
ch=sumh.count(maxh)
cw=sumw.count(maxw)
#print(maxh,maxw,ch,cw)

#爆弾のある場所がH,Wの座標で両方共で最大個数の場所であった場合その数を加算
count=0
for h,w in bomb:
    if sumh[h-1]==maxh and sumw[w-1]==maxw:
        count+=1
#print(count)

#破壊できる数は、そのマスに爆破対象があるとき一つ減ってしまう。
if count==ch*cw:
    print(maxh+maxw-1)
else:
  print(maxh+maxw)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
a=[0]*h;b=[0]*w
s=set()
for _ in range(m):
  x,y=map(lambda x:int(x)-1,input().split())
  a[x]+=1;b[y]+=1
  s.add(x*10**6+y)
ma=max(a);mb=max(b)
c=[i for i,v in enumerate(a) if v==ma]
d=[i for i,v in enumerate(b) if v==mb]
for x in c:
  for y in d:
    if not(x*10**6+y in s):
      print(ma+mb)
      exit()
print(ma+mb-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
bomb = []
h_sum = [0]*W
w_sum = [0]*H
for _ in range(M):
    h, w = map(int, input().split())
    bomb.append((h,w))
    h_sum[w-1] += 1
    w_sum[h-1] += 1
max_h = max(h_sum)
max_w = max(w_sum)
target_cnt = h_sum.count(max_h)*w_sum.count(max_w)
for h, w in bomb:
    if h_sum[w-1] == max_h and w_sum[h-1] == max_w:
        target_cnt -= 1
if target_cnt == 0:
    print(max_h+max_w-1)
else:
    print(max_h+max_w)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
B = [0]*M
a,b = 0,0
HOR = [0]*H
VER = [0]*W
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    HOR[a] += 1
    VER[b] += 1
    B[i] = (a,b)

max_hor_num = -1
max_hor_set = set()
for i in range(H):
    a = HOR[i]
    if max_hor_num == a:
        max_hor_set.add(i)
    elif max_hor_num < a:
        max_hor_set = set()
        max_hor_set.add(i)
        max_hor_num = a

max_ver_num = -1
max_ver_set = set()
for i in range(W):
    a = VER[i]
    if max_ver_num == a:
        max_ver_set.add(i)
    elif max_ver_num < a:
        max_ver_set = set()
        max_ver_set.add(i)
        max_ver_num = a

#print(*max_hor_set)
#print(*max_ver_set)

empty = len(max_hor_set) * len(max_ver_set)
count = 0

if empty > M:
    print(max_hor_num+max_ver_num)
    exit()
for h,w in B:
    if (h in max_hor_set) and (w in max_ver_set):
        count += 1
    if count == empty:
        print(max_hor_num+max_ver_num-1)
        exit()
print(max_hor_num+max_ver_num)

Submission status: Accepted

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


@njit(cache=True)
def f(h,w,m,yp,xp,s):
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    ans = 0
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


h,w,m = map(int,input().split())
s = set()
yp = np.zeros((h,2),dtype=np.int)
xp = np.zeros((w,2),dtype=np.int)
yp[:,1] = np.arange(h)
xp[:,1] = np.arange(w)
for i in range(m):
    hi,wi = map(int,input().split())
    s.add((hi-1,wi-1))
    yp[hi-1,0] += 1
    xp[wi-1,0] += 1
ans = f(h,w,m,yp,xp,s)
print(ans)

Submission status: Accepted

Solution code:
H, W, M, *HW = map(int, open(0).read().split())
HW = list(zip(*[iter(HW)] * 2))

A = [0] * (H + 1)
B = [0] * (W + 1)
for h, w in HW:
    A[h] += 1
    B[w] += 1

a = max(A)
b = max(B)

cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])

print(a + b - (cnt == 0))

Submission status: Accepted

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

H,W=[0]*h,[0]*w
for i,j in HW:
    H[i-1] +=1
    W[j-1] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

Submission status: Accepted

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

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal, ROUND_CEILING
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W, M = MAP()

h, w = ZIP(M)
cnt_h = Counter(h)
hm = max(cnt_h.values())
cnt_w = Counter(w)
wm = max(cnt_w.values())
hl = [k for k, v in cnt_h.items() if v == hm]
wl = [k for k, v in cnt_w.items() if v == wm]

s = set()
for h_, w_ in zip(h, w):
    s.add((h_, w_))

ans = hm + wm

for i in hl:
    for j in wl:
        if (i, j) not in s:
            break
    else:
        continue
    break
else:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    h, w, m = map(int,input().split())
    bomb = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
    x = [0] * h
    y = [0] * w

    for h,w in bomb:
        x[h] +=1
        y[w] +=1

    maxX = max(x)
    maxY = max(y)

    r = [h for h,x in enumerate(x) if x == maxX]
    c = [w for w,y in enumerate(y) if y == maxY]

    bomb = set(bomb)
    
    for ri in r:
        for ci in c:
            if (ri,ci) not in bomb:
                print(maxX + maxY)
                sys.exit()
    print(maxX + maxY -1)
    
main()