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:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

H, W, M = MAP()
row = [0] * (H+1)
col = [0] * (W+1)
se = set()
for i in range(M):
    h, w = MAP()
    row[h] += 1
    col[w] += 1
    se.add((h, w))

mxh = max(row)
hli = []
for h, cnt in enumerate(row):
    if cnt == mxh:
        hli.append(h)
mxw = max(col)
wli = []
for w, cnt in enumerate(col):
    if cnt == mxw:
        wli.append(w)

ok = 0
for h in hli:
    for w in wli:
        if (h, w) not in se:
            ok = 1
            break
    if ok:
        break
ans = mxh + mxw - 1 + ok
print(ans)

Submission status: Accepted

Solution code:
def max_bomb_set(l):
    l.sort(key=lambda x: x[0], reverse=True)
    res = []
    for cnt, tag in l:
        if cnt == l[0][0]:
            res.append(tag)
        else:
            break
    return res, l[0][0]


def main():
    h, w, m = map(int, input().split())
    height = [[0, i] for i in range(h)]
    width = [[0, i] for i in range(w)]
    target = set()
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        target.add((x, y))
        height[x][0] += 1
        width[y][0] += 1
    max_height, max_h_val = max_bomb_set(height)
    max_width, max_w_val = max_bomb_set(width)
    ans = max_h_val + max_w_val
    for hh in max_height:
        for ww in max_width:
            if (hh, ww) not in target:
                return ans
    return ans - 1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys

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


hlis=[0 for i in range(h)]
wlis=[0 for i in range(w)]
hw=[]

for i in range(m):
  hi,wi=map(int,input().split())
  hlis[hi-1]+=1
  wlis[wi-1]+=1
  hw.append([hi-1,wi-1])

hmax=max(hlis)
wmax=max(wlis)

ph=[]
pw=[]
for i in range(h):
  if hlis[i]==hmax:
    ph.append(i)
for i in range(w):
  if wlis[i]==wmax:
    pw.append(i)

if len(ph)*len(pw)>3*(10**5):
  print(hmax+wmax)
  sys.exit()

plis=[]
for phi in ph:
  for pwj in pw:
    plis.append(phi*(10**6)+pwj)

plis.sort()

hwlis=[]
for hi,wi in hw:
  hwlis.append(hi*(10**6)+wi)

hwlis.sort()
    
c=0
check=0

for pi in plis:
  while pi!=hwlis[c]:
    c+=1
    if c>=len(hwlis):
      check=1
      break
  if check==1:
    break

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

Submission status: Accepted

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

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

bomb_h = [0] * H
bomb_w = [0] * W
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    bomb.add((h-1, w-1))

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if (h, w) not in bomb:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
g=[]
e1=[0]*h
e2=[0]*w
for c in range(m):
    a,b=map(int,input().split())
    g.append([a-1,b-1])
    e1[a-1]+=1
    e2[b-1]+=1
p1=max(e1)
p2=max(e2)
x=[1 if e1[c]==p1 else 0 for c in range(h)]
y=[1 if e2[c]==p2 else 0 for c in range(w)]
r=sum(x)*sum(y)
for i in g:
    if x[i[0]]==1 and y[i[1]]==1:
        r-=1
if r==0:
    print(p1+p2-1)
else:
    print(p1+p2)

Submission status: Accepted

Solution code:
h,w,m=list(map(int, input("").split()))
bo=[]
hb=[0]*h
wb=[0]*w
for i in range(m):
    a,b=list(map(int, input("").split()))
    #各行列に爆弾いくつあるか
    hb[a-1]+=1
    wb[b-1]+=1
    #爆弾の座標
    bo.append([a,b])
#ソート
mwb=[]
mhb=[]
#爆弾数が最大の行と列番号をメモ
hmax=max(hb)
wmax=max(wb)
for i in range(h):
    if hb[i]==hmax:
        mhb.append(i+1)
for i in range(w):
    if wb[i]==wmax:
        mwb.append(i+1)
c=0
#最大の爆弾数の行と列に含まれる爆弾数=cの確認
for h,w in bo:
     #h in mhb and w in mwb
    if(hb[h-1] == hmax and wb[w-1] == wmax):
        c+=1
#行と列の最大爆弾数の和
out=hmax+wmax
#行と列の最大数の積がcと一致するなら必ず重複があるので－1
if c==len(mwb)*len(mhb):
    out-=1
print(out)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
objs=[tuple(map(int,input().split())) for i in range(m)]
setobj=set(objs)
xs,ys=zip(*objs)
from collections import Counter as co
xs,ys=co(xs),co(ys)
xim,yim=xs.most_common(1)[0][1], ys.most_common(1)[0][1]
A=len([1 for u in xs.values() if u==xim])* len([1 for u in ys.values() if u==yim])
for a,b in setobj:
  if xs[a]==xim and ys[b]==yim:A-=1

print(xim+yim-1+int(A>0))

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
cntH = {}
cntW = {}
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb.add((h-1, w-1))
    cntH[h-1] = cntH.get(h-1, 0) + 1
    cntW[w-1] = cntW.get(w-1, 0) + 1

maxH, maxW = max(cntH.values()), max(cntW.values())
max_H_list = [kv[0] for kv in cntH.items() if kv[1] == maxH]
max_W_list = [kv[0] for kv in cntW.items() if kv[1] == maxW]

ans = maxH + maxW - 1
flag = False
for i in max_H_list:
    for j in max_W_list:
        if (i, j) not in bomb:
            flag = True
            break
    else:
        continue
    break
if flag:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

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

y_to_num = [0] * h
x_to_num = [0] * w
existing_h_to_w = defaultdict(set)


for _ in range(m):
    hh, ww = map(lambda x: int(x), input().split())
    y_to_num[hh-1] += 1
    x_to_num[ww-1] += 1
    existing_h_to_w[hh-1].add(ww-1)

max_vertical_num = max(y_to_num)
max_horizontal_num = max(x_to_num)

y_coor_with_max_num = [i for i, num in enumerate(y_to_num) if num == max_vertical_num]
x_coor_with_max_num = [i for i, num in enumerate(x_to_num) if num == max_horizontal_num]

# print(y_coor_with_max_num, x_coor_with_max_num, existing_h_to_w)

for y in y_coor_with_max_num:
    for x in x_coor_with_max_num:
        if x not in existing_h_to_w[y]:
            print(max_vertical_num + max_horizontal_num)
            sys.exit()

print(max_vertical_num + max_horizontal_num - 1)

Submission status: Accepted

Solution code:
h,w,m=list(map(int, input("").split()))
bo=[]
hb=[0]*h
wb=[0]*w
for i in range(m):
    a,b=list(map(int, input("").split()))
    #各行列に爆弾いくつあるか
    hb[a-1]+=1
    wb[b-1]+=1
    #爆弾の座標
    bo.append([a,b])
#ソート
mwb=[]
mhb=[]
#爆弾数が最大の行と列番号をメモ
hmax=max(hb)
wmax=max(wb)
for i in range(h):
    if hb[i]==hmax:
        mhb.append(i)
for i in range(w):
    if wb[i]==wmax:
        mwb.append(i)
c=0
#最大の爆弾数の行と列に含まれる爆弾数=cの確認
for h,w in bo:
     #h in mhb and w in mwb
    if(hb[h-1] == hmax and wb[w-1] == wmax):
        c+=1
#行と列の最大爆弾数の和
out=hmax+wmax
#行と列の最大数の積がcと一致するなら必ず重複があるので－1
if c==len(mwb)*len(mhb):
    out-=1
print(out)

Submission status: Accepted

Solution code:
import numpy as np
import itertools


def pd(s):
    # print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)
targets = {}
for h, w in ms:
    rows[h] += 1
    cols[w] += 1
    targets[f"{h},{w}"] = True

rmax = max(rows)
cmax = max(cols)
rmax_hs = [i for i, v in enumerate(rows) if v == rmax]
cmax_wh = [i for i, v in enumerate(cols) if v == cmax]

for h, w in itertools.product(rmax_hs, cmax_wh):
    if f"{h},{w}" not in targets:
        print(rmax + cmax)
        exit()
print(rmax + cmax - 1)

Submission status: Accepted

Solution code:
*r,=c=[0]*9**6
_,*z=[[*map(int,t.split())]for t in open(0)]
for y,x in z:r[y]+=1;c[x]+=1
print(-(r.count(h:=max(r))*c.count(w:=max(c))==sum(h+w==r[y]+c[x]for y,x in z))+h+w)

Submission status: Accepted

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

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0

maxed_h = set([h for h in range(H) if row[h] == r_max])
maxed_w = set([w for w in range(W) if col[w] == c_max])
bomb_option_sites_n = len(maxed_h)*len(maxed_w)
targets_on_bomb_option = 0
for th, tw in targets:
    if th in maxed_h and tw in maxed_w:
        targets_on_bomb_option += 1

if bomb_option_sites_n == targets_on_bomb_option:
    print(r_max + c_max - 1)
else:
    print(r_max + c_max)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main()->str:
    H,W,M=map(int,input().split())
    ch=[0]*H
    cw=[0]*W
    bm=defaultdict(lambda:False)
    for _ in range(M):
        h,w=map(int,input().split())
        h-=1
        w-=1
        bm[(h,w)]=True
        ch[h]+=1
        cw[w]+=1
    hb=max(ch)
#    max_h=[i for i, x in enumerate(ch) if x == hb]
    max_h=[]
    for i in range(len(ch)):
        if ch[i]==hb: max_h.append(i)
    wb=max(cw)
#    max_w=[i for i, x in enumerate(cw) if x == wb]
    max_w=[]
    for i in range(len(cw)):
        if cw[i]==wb: max_w.append(i)
    
    z=hb+wb
    for mh in max_h:
        for mw in max_w:
            if bm[(mh,mw)]==False:
                return(z)
    return(z-1)

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

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
listh = [0] * H
listw = [0] * W
s = set()
for i in range(M):
    hm,wm = map(int,input().split())
    listh[hm-1] += 1
    listw[wm-1] += 1
    s.add((hm-1,wm-1))
mh = max(listh)
mw = max(listw)
maxh = [i for i,v in enumerate(listh) if v == mh]
maxw = [i for i,v in enumerate(listw) if v == mw]

import sys
for i in maxh:
    for j in maxw:
        if (i,j) not in s:
            print(mh + mw)
            sys.exit()
print(mh + mw - 1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools


def pd(s):
    #print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)
bombs = {}
for h,w in ms:
    rows[h] += 1
    cols[w] += 1
    bombs[f"{h},{w}"] = True

rmax = max(rows)
cmax = max(cols)
rmax_hs = [i for i, v in enumerate(rows) if v == rmax]
cmax_wh = [i for i, v in enumerate(cols) if v == cmax]

for h,w in itertools.product(rmax_hs, cmax_wh):
    if f"{h},{w}" not in bombs:
        print(rmax + cmax)
        exit()
print(rmax + cmax - 1)

Submission status: Accepted

Solution code:
h,w,m = map(int, input().split())
bh = []
bw = []
l_num = [0]*h
c_num = [0]*w
for i in range(m):
    i1, i2 = map(int, input().split())
    bh.append(i1)
    bw.append(i2)
    l_num[i1-1] = l_num[i1-1] + 1
    c_num[i2-1] = c_num[i2-1] + 1

#print(l_num,c_num)

max_l_num = max(l_num)
max_c_num = max(c_num)
l_candi = [i for i, v in enumerate(l_num) if v == max_l_num]
c_candi = [i for i, v in enumerate(c_num) if v == max_c_num]

#print(l_candi,c_candi)

t = 0
for k in range(m):
    if l_num[bh[k]-1] == max_l_num and c_num[bw[k]-1] == max_c_num:
        t = t + 1

if t < len(l_candi)*len(c_candi):
    print(max_l_num+max_c_num)
else:
    print(max_l_num+max_c_num-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = set()
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb.add((y, x))
        
    kouho_h = []
    kouho_w = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    for i in kouho_h:
        for j in kouho_w:
            if (i, j) not in bomb:
                print(max_h + max_w)
                exit()
    print(max_h + max_w - 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import random

def putmx(lis,mx):
  ret=[]
  for (i,j) in zip(range(len(lis)),lis):
    if j==mx:
      ret.append(i)
  return ret
  

h,w,m=map(int,input().split())
hb=[0]*h
wb=[0]*w
bmb=[]
for i in range(h):
  bmb.append({-1})
for i in range(m):
  hh,ww=map(int,input().split())
  hh-=1
  ww-=1
  bmb[hh].add(ww)
  hb[hh]+=1
  wb[ww]+=1
mhb=max(hb)
mwb=max(wb)
hmx=putmx(hb,mhb)
wmx=set(putmx(wb,mwb))

#print(hb,wb,hmx,wmx)
fl=False
for i in hmx:
  if wmx|bmb[i]!=bmb[i]:
    print(mhb+mwb)
    break
else:
  print(mhb+mwb-1)

#print(hmx,wmx,bmb)

Submission status: Accepted

Solution code:
# from bisect import bisect_left
import sys
input = sys.stdin.readline
H,W,m = map(int,input().split())
h = [0]*(H+1)
w = [0]*(W+1)
c = [{-1,10**6} for i in range(H+1)]
for i in range(m):
    a,b = map(int,input().split())
    h[a] += 1
    w[b] += 1
    c[a].add(b)
mh = max(h)
mw = max(w)
# hkouho = []
# wkouho = []
hkouho= [i for i in range(H+1) if h[i] == mh]
wkouho= [i for i in range(W+1) if w[i] == mw]
# for i in range(H+1):
#     if h[i] == mh:
#         hkouho.append(i)
# for i in range(W+1):
#     if w[i] == mw:
#         wkouho.append(i)
for i in hkouho:
    # c[i] = set(c[i])
    for j in wkouho:
        # if c[i][bisect_left(c[i],j)] != j:
        if j not in c[i]:
            print(mh+mw)
            exit()
print(mh+mw-1)

Submission status: Accepted

Solution code:
import numpy as np


def pd(s):
    # print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)
bombs = {}
for m in ms:
    h = m[0]
    w = m[1]
    rows[h] += 1
    cols[w] += 1
    bombs[f"{h},{w}"] = True

rmax = max(rows)
cmax = max(cols)
rmax_hs = [i for i, v in enumerate(rows) if v == rmax]
cmax_wh = [i for i, v in enumerate(cols) if v == cmax]

for h in rmax_hs:
    for w in cmax_wh:
        if f"{h},{w}" not in bombs:
            print(rmax + cmax)
            exit()
print(rmax + cmax - 1)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    H,W,m=map(int, input().split())
    Hline=[]
    wline=[]
    blist=dict()
    for k in range(m):
        h,w=map(int, input().split())
        Hline.append(h)
        wline.append(w)
        blist[h*(W+2)+w]=0
    hc=Counter(Hline).most_common()
    wc=Counter(wline).most_common()
    ans=hc[0][1]+wc[0][1]
    hl=[]
    wl=[]
    for hcc in hc:
        if hcc[1]!= hc[0][1]:
            break
        hl.append(hcc[0])
    for wcc in wc:
        if wcc[1]!= wc[0][1]:
            break
        wl.append(wcc[0])
    for hll in hl:
        for wll in wl:
            if hll*(W+2)+wll not in blist:
                print(ans)
                exit()
    print(ans-1)
 
    
        
 
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x,y,m = map(int,input().split())
row = {}
ch = set()
column = {}
for i in range(m):
	h,k = map(int,input().split())
	ch.add((h,k))
	if h in row:
		row[h] += 1
	else:
		row[h] = 1

	if k in column:
		column[k] += 1
	else:
		column[k] = 1


r_max = 0
c_max = 0

for i in row:
	r_max = max(r_max,row[i])
for j in column:
	c_max = max(c_max,column[j])

r_inx = []
w_inx = []

for i in row:
	if row[i] == r_max:
		r_inx.append(i)
for j in column:
	if column[j] == c_max:
		w_inx.append(j)

flag = 0
for i in r_inx:
	for j in w_inx:
		if (i,j) not in ch:
			flag = 1
			break
if flag == 0:
	print(r_max+c_max-1)
else:
	print(r_max+c_max)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

bombw = [0]*w
bombh = [0]*h
dd = defaultdict(bool)
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    dd[str(hi-1)+"-"+str(wi-1)] = True
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if not dd[str(i)+"-"+str(j)]:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
flag = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) not in m.keys():
            flag = 1
            break

if flag == 1:
    print(int(h_max + w_max))
else:
    print(int(h_max + w_max - 1))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W, M = MI()
    Hlist = [[0, i] for i in range(H)]
    Wlist = [[0, i] for i in range(W)]
    Dlist = [set() for i in range(H)]
    H_max = -float('inf')
    W_max = -float('inf')
    
    for i in range(M):
        h, w = MI()
        Hlist[h-1][0]+=1
        Wlist[w-1][0]+=1
        Dlist[h-1] |= {w-1}
        H_max = max(H_max, Hlist[h-1][0])
        W_max = max(W_max, Wlist[w-1][0])
    Hlist = set([temp[1] for temp in Hlist if temp[0] == H_max])
    Wlist = set([temp[1] for temp in Wlist if temp[0] == W_max])
    ans = H_max+W_max-1

    for index1 in Hlist:
        for index2 in Wlist:
            if not index2 in Dlist[index1]:
                ans += 1
                break
        else:
            continue
        break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
A = [0]*H
B = [0]*W
D = set()
for _ in range(M):
    h,w = map(int, input().split())
    A[h-1] += 1
    B[w-1] += 1
    D.add((h-1,w-1))
a, b = max(A), max(B)
res = a+b-1
E, F = [], []
for i in range(H):
    if A[i] == a:
        E.append(i)
for j in range(W):
    if B[j] == b:
        F.append(j)
for i in E:
    for j in F:
        if (i,j) not in D:
            print(res+1)
            exit()
print(res)

Submission status: Accepted

Solution code:
import numpy as np
import itertools


def pd(s):
    #print(s)
    pass


# input
H, W, M = map(int, input().split())
ms = [
    [int(i) for i in input().split()]
    for m in range(M)
]
pd(f"{H=} {W=} {M=}")
pd(f"{ms=}")

rows = [0]*(H+1)
cols = [0]*(W+1)
bombs = {}
for m in ms:
    h = m[0]
    w = m[1]
    rows[h] += 1
    cols[w] += 1
    bombs[f"{h},{w}"] = True

rmax = max(rows)
cmax = max(cols)
rmax_hs = [i for i, v in enumerate(rows) if v == rmax]
cmax_wh = [i for i, v in enumerate(cols) if v == cmax]

for m in itertools.product(rmax_hs, cmax_wh):
    h = m[0]
    w = m[1]
    if f"{h},{w}" not in bombs:
        print(rmax + cmax)
        exit()
print(rmax + cmax - 1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
a=[0]*h
b=[0]*w
hw=[]
for _ in range(m):
    hh,ww=map(int,input().split())
    hw+=((hh-1,ww-1)),
    a[hh-1]+=1
    b[ww-1]+=1
    
ma=max(a)
mb=max(b)

# x_ind=[i for i,j in enumerate(a) if j==ma]
# y_ind=[i for i,j in enumerate(b) if j==mb]



cnt=0
# sonzai suru

for i,j in hw:
    if a[i]==ma and b[j]==mb:cnt+=1

if cnt==a.count(ma)*b.count(mb):
    print(ma+mb-1)
else:
    print(ma+mb)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline
H,W,m = map(int,input().split())
h = [0]*(H+1)
w = [0]*(W+1)
c = [{-1,10**6} for i in range(H+1)]
for i in range(m):
    a,b = map(int,input().split())
    h[a] += 1
    w[b] += 1
    c[a].add(b)
mh = max(h)
mw = max(w)
hkouho = []
wkouho = []
for i in range(H+1):
    if h[i] == mh:
        hkouho.append(i)
for i in range(W+1):
    if w[i] == mw:
        wkouho.append(i)
for i in hkouho:
    # c[i] = set(c[i])
    for j in wkouho:
        # if c[i][bisect_left(c[i],j)] != j:
        if j not in c[i]:
            print(mh+mw)
            exit()
print(mh+mw-1)

Submission status: Accepted

Solution code:
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
  
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
 
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す
 
for i in range(M):
    goukei = int(countleft.get(c[i][0])) + int(countright.get(c[i][1]))
    if goukei == tempmax:
        cnt += 1
    else:
        pass

if cnt == int(leftkeyN * rightkeyN):
    print(int(tempmax - 1))
else:
    print(int(tempmax))

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline
H,W,m = map(int,input().split())
h = [0]*(H+1)
w = [0]*(W+1)
c = [[-1,10**6] for i in range(H+1)]
for i in range(m):
    a,b = map(int,input().split())
    h[a] += 1
    w[b] += 1
    c[a].append(b)
mh = max(h)
mw = max(w)
hkouho = []
wkouho = []
for i in range(H+1):
    if h[i] == mh:
        hkouho.append(i)
for i in range(W+1):
    if w[i] == mw:
        wkouho.append(i)
for i in hkouho:
    c[i] = set(c[i])
    for j in wkouho:
        # if c[i][bisect_left(c[i],j)] != j:
        if j not in c[i]:
            print(mh+mw)
            exit()
print(mh+mw-1)

Submission status: Accepted

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

sum_h = [0] * W
sum_w = [0] * H
bomb_list = set()

for _ in range(M):
    h, w = [int(i) for i in input().split()]
    h -= 1
    w -= 1
    bomb_list.add((h,w))
    sum_h[w] += 1
    sum_w[h] += 1

max_sum_h = max(sum_h)
max_sum_w = max(sum_w)
output = max_sum_h + max_sum_w - 1

max_bombs_h = [h for h in range(H) if sum_w[h] == max_sum_w]
max_bombs_w = [w for w in range(W) if sum_h[w] == max_sum_h]

for h in max_bombs_h:
    for w in max_bombs_w:
        if (h, w) not in bomb_list:
            output = max_sum_h + max_sum_w
            break
        else:
            continue
        break
        
print(output)

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline().strip()
from collections import defaultdict

def main():
    H, W, M = map(int,input().split())
    
    d_row = defaultdict(int)
    d_col = defaultdict(int)
    hw = []

    for _ in range(M):
        h, w = map(int, input().split())
        h -= 1
        w -= 1
        d_row[h] += 1
        d_col[w] += 1
        hw.append((h, w))


    max_row_val = max(d_row.values())
    max_col_val = max(d_col.values())

    max_rows = set(key for key, val in d_row.items() if val == max_row_val)
    max_cols = set(key for key, val in d_col.items() if val == max_col_val)
   
    if len(max_rows)*len(max_cols) == sum((h in max_rows and w in max_cols) for h, w in hw):
        ans = max_row_val + max_col_val - 1
    else:
        ans = max_row_val + max_col_val
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
sumw=[set() for _ in range(w)]
sumh=[0]*h
for _ in range(m):
    hi,wi=map(int,input().split())
    hi-=1
    wi-=1
    sumh[hi]+=1
    sumw[wi].add(hi)
maxi=0
for i in range(w):
    maxi=max(maxi,len(sumw[i]))
s=set([i for i in range(h)])
for i in range(w):
    if len(sumw[i])==maxi:
        s=s&sumw[i]
ans=0
#print(sumw)
for i in range(h):
    if i not in s:
        ans=max(ans,sumh[i]+maxi)
    else:
        ans=max(ans,sumh[i]+maxi-1)
print(ans)

Submission status: Accepted

Solution code:
import sys

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

h_obj = [0 for _ in range(H)]
w_obj = [0 for _ in range(W)]
objs = set()
for _ in range(M):
    h, w = map(int, sys.stdin.readline().split())
    h -= 1
    w -= 1
    h_obj[h] += 1
    w_obj[w] += 1
    objs.add((w, h))

ans = 0
h_max = max(h_obj)
w_max = max(w_obj)
h_cond = set()
w_cond = set()
for i in range(W):
    if w_max == w_obj[i]:
        w_cond.add(i)
for i in range(H):
    if h_max == h_obj[i]:
        h_cond.add(i)

# print(h_cond, w_cond)
ans = h_max + w_max
for w in w_cond:
    for h in h_cond:
        if (w, h) not in objs:
            print(ans)
            sys.exit()

print(ans - 1)

Submission status: Accepted

Solution code:
H, W, m = map(int, input().split())
hs = [0] * (H+1)
ws = [0] * (W+1)
from collections import defaultdict
d = defaultdict(bool)
N = 10**6
for i in range(m):
    hi,wi = map(int, input().split())
    hi -= 1
    wi -= 1
    hs[hi] += 1
    ws[wi] += 1
    d[hi*10**6+wi] = True

hmx = max(hs)
hset = set()
for i,h in enumerate(hs):
    if h == hmx:
        hset.add(i)
wmx = max(ws)
wset = set()
for j, w in enumerate(ws):
    if w == wmx:
        wset.add(j)

flg = False
ans = 0
cnt = 0
for i in hset:
    for j in wset:
        ans = max(ans, hmx+wmx-d[i*N+j]) 
        if cnt >= m:
            flg = True
            break
        cnt += 1
    if flg:break

print(ans)

Submission status: Accepted

Solution code:
h,w,m = map(int, input().split())
hw = [list(map(int, input().split())) for i in range(m)]
bomb = set()
h_list = [0] * (h+1)
w_list = [0] * (w+1)
for H,W in hw:
  h_list[H] += 1
  w_list[W] += 1
  bomb.add((H,W))
max_h = max(h_list)
max_w = max(w_list)
maxh_list = []
maxw_list = []
for k,v in enumerate(h_list):
  if v == max_h:
    maxh_list.append(k)
for k,v in enumerate(w_list):
  if v == max_w:
    maxw_list.append(k)
if len(maxh_list) * len(maxw_list) > m:
  ans = max_h + max_w
else:
  ans = max_h + max_w - 1
  for i in maxh_list:
    for j in maxw_list:
      if (i,j) not in bomb:
        ans = max_h + max_w
        break
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

HW = set(HW)
for h in hs:
    for w in ws:
        if (h+1, w+1) not in HW:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)

Submission status: Accepted

Solution code:
*r,=c=[0]*9**6
_,*z=[[*map(int,t.split())]for t in open(0)]
for y,x in z:r[y]+=1;c[x]+=1
h,w=max(r),max(c)
print(h+w-(r.count(h)*c.count(w)==sum(h+w==r[y]+c[x]for y,x in z)))

Submission status: Accepted

Solution code:
H,W,M = [int(x) for x in input().split()]
hw = []
hNum = [0]*H
wNum = [0]*W

for i in range(M):
    h,w = [int(x) for x in input().split()]
    hw.append([h,w])
    hNum[h-1]+=1
    wNum[w-1]+=1

hmax = max(hNum)
hMaxList = []
wmax = max(wNum)
wMaxList = []

for i in range(H):
    if(hmax == hNum[i]):
        hMaxList.append(i)
for i in range(W):
    if(wmax == wNum[i]):
        wMaxList.append(i)

ans = wmax + hmax
count = 0
for i in hw:
    if(hNum[i[0]-1] == hmax and wNum[i[1]-1] == wmax):
        count += 1
# if(hNum.count(hmax) * wNum.count(wmax) == count):
if(len(hMaxList) * len(wMaxList) == count):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W, M = NMI()
    bombs = defaultdict(int)
    rows = [0]*H
    cols = [0]*W
    for _ in range(M):
        h, w = NMI()
        h, w = h-1, w-1
        bombs[h * 10**6 + w] = 1
        rows[h] += 1
        cols[w] += 1
    rows_i = [[r, i] for i, r in enumerate(rows)]
    cols_i = [[c, i] for i, c in enumerate(cols)]
    rows_i.sort(reverse=True)
    cols_i.sort(reverse=True)

    rmax = rows_i[0][0]
    cmax = cols_i[0][0]
    for r, i in rows_i:
        if r <= rmax - 1:
            break
        for c, j in cols_i:
            if c <= cmax - 1:
                break
            if i * 10**6 + j not in bombs:
                print(rmax + cmax)
                exit()
    print(cmax+rmax-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
r = [0]*(W+1)
c = [0]*(H+1)
rc = {}
for i in range(M):
    h, w = map(int, input().split())
    rc[(h, w)] = True
    r[w] += 1
    c[h] += 1

rm = max(r)
cm = max(c)

ri = {i for i, v in enumerate(r) if v == rm}
ci = {i for i, v in enumerate(c) if v == cm}

cnt = sum([w in ri and h in ci for h, w in rc])
print(rm+cm-(len(ri)*len(ci) == cnt))