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:
from collections import deque,defaultdict
import heapq as hp
def solve():
    h,w,m=map(int,input().strip().split(" "))
    dr=defaultdict(int)
    dc=defaultdict(int)
    s=set()
    for _ in range(m):
        a,b=map(int,input().strip().split(" "))
        dr[a]+=1
        dc[b]+=1
        s.add((a,b))

    kr=max(dr.values())
    kc=max(dc.values())
    rs=[]
    cs=[]
    rs+=[i for i in dr.keys() if dr[i]==kr ]
    cs+=[i for i in dc.keys() if dc[i]==kc ]
    for i in rs:
        for j in cs:
            if (i,j) not in s:
                print(kr+kc)
                exit()

    print(kr+kc-1)






solve()

Submission status: Accepted

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

visited = set()

h_sum = [0] * H
w_sum = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    visited.add((h, w))
    h_sum[h] += 1
    w_sum[w] += 1

max_h = max_w = 0
can_h = []
can_w = []
for i in range(H):
    max_h = max(max_h, h_sum[i])
    
for i in range(W):
    max_w = max(max_w, w_sum[i])

for i in range(H):
    if h_sum[i] == max_h:
        can_h.append(i)
for i in range(W):
    if w_sum[i] == max_w:
        can_w.append(i)
        
ans = max_h + max_w

for i in can_h:
    for j in can_w:
        if (i, j) not in visited:
            print(ans)
            exit()

print(ans-1)

Submission status: Accepted

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

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

row = [0]*h
col = [0]*w
enemy = []

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

enemy = set(enemy)
rmax = max(row)
cmax = max(col)

on_r = row.count(rmax)
on_c = col.count(cmax)

on = 0
for hh, ww in enemy:
    if row[hh] == rmax and col[ww] == cmax:
        on += 1
if on == on_r*on_c:
    print(rmax+cmax-1)
else:
    print(rmax+cmax)

Submission status: Accepted

Solution code:
import sys
import numpy as np
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    h, w, m = MII()
    bombs = [MIIZ() for _ in range(m)]
    a = [0]*h
    b = [0]*w
    for y,x in bombs:
        a[y] += 1
        b[x] += 1
    maxa = max(a)
    maxb = max(b)
    sumv = maxa + maxb
    c = a.count(maxa)*b.count(maxb) - sum(a[y]+b[x] == sumv for y,x in bombs)
    print(sumv - (c<=0))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int,input().split())
row = [0]*H
col = [0]*W
target = set()
for i in range(M):
    h,w = map(int,input().split())
    row[h-1] += 1
    col[w-1] += 1
    target.add((h-1,w-1))
ans = -1
for h,w in target:
    ans = max(ans, row[h]+col[w]-1)
A = max(row)
B = max(col)
a = [x for x in range(H) if row[x] == A]
b = [x for x in range(W) if col[x] == B]
cnt = 0
for i in a:
    for j in b:
        cnt += 1
        if (i,j) not in target:
            print(A+B)
            exit(0)
        if cnt > M:
            print(A+B-1)
            exit(0)
print(A+B-1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
hs=[0 for _ in range(h)]
ws=[0 for _ in range(w)]
B=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  hs[a]+=1
  b-=1
  ws[b]+=1
  B.add((a,b))
hmax=-1
wmax=-1
for i in range(h):
  hmax=max(hmax,hs[i])
for j in range(w):
  wmax=max(wmax,ws[j])
mh=[]
mw=[]
for i in range(h):
  if hs[i]==hmax:
    mh.append(i)
for j in range(w):
  if ws[j]==wmax:
    mw.append(j)

ans=hmax+wmax
cnt=0
for i in mh:
  for j in mw:
    if (i,j) in B:
      continue
    print(ans)
    exit()
print(ans-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

H, W, M = list(map(int, input().split()))
hw = [list(map(int, input().split())) for _ in range(M)]

d1 = defaultdict(int)
d2 = defaultdict(int)

b = defaultdict(int)

for h, w in hw:
    d1[h] += 1
    d2[w] += 1
    b[(h, w)] = 1

m1 = max(d1.values())
m2 = max(d2.values())

e1 = [k for k in d1.keys() if d1[k] == m1]
e2 = [k for k in d2.keys() if d2[k] == m2]

flag = True

for x in e1:
    for y in e2:
        if b[(x, y)] == 1:
            pass
        else:
            flag = False
            break
    if not flag:
        break

if flag:
    print(m1+m2-1)
else:
    print(m1+m2)

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    
    target_h = {}
    target_w = {}
    target_hw = set()
    for h, w in targets:
        target_h[h] = target_h.setdefault(h, 0) + 1
        target_w[w] = target_w.setdefault(w, 0) + 1
        target_hw.add((h, w))

    max_h = max(target_h.values())
    max_w = max(target_w.values())

    h_set = {h for h, v in target_h.items() if max_h == v}
    w_set = {w for w, v in target_w.items() if max_w == v}

    ans = max_h + max_w - 1
    for hw in itertools.product(h_set, w_set):
        if hw not in target_hw:
            ans += 1
            break
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
h,w,m = map(int,input().split())
dh = defaultdict(int)
dw = defaultdict(int)
l=defaultdict(tuple)
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[(x,y)]=1
m = 0
for i in range(1,h+1):
    if dh[i]>m:
        m = dh[i]
        hi=i
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[(hi,i)]==1:
        d-=1
    m = max(m,d)
c+=m
m = 0
wi=0
for i in range(1,w+1):
    if dw[i]>m:
        m = dw[i]
        wi=i
c2=m
m = 0
for i in range(1,h+1):
    d = dh[i]
    if l[(i,wi)]==1:
        d-=1
    m = max(m,d)
c2+=m
print(max(c,c2))

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
hl=[0]*(h)
wl=[0]*(w)
bom=[]
for i in range(m):
  h1,w1=map(int,input().split())
  bom.append([h1-1,w1-1])
  hl[h1-1]+=1
  wl[w1-1]+=1

mh=max(hl)
mw=max(wl)
ans=mh+mw
mhl=set()
mwl=set()
for i in range(h):
  if mh==hl[i]:
    mhl.add(i)
    
for i in range(w):
  if mw==wl[i]:
    mwl.add(i)

count=len(mhl)*len(mwl)
for i in range(len(bom)):
  if bom[i][0] in mhl and bom[i][1] in mwl:
    count-=1
if count>0:
  print(ans)
else:
  print(ans-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 main():
    H, W, M = map(int, input().split())
    # H, W, M = (3 * 10 ** 5, 3 * 10 ** 5, 3 * 10 ** 5)

    row = [0] * (H + 1)
    row_set = [set() for _ in range(H+1)]
    column = [0] * (W + 1)
    column_set = [set() for _ in range(W+1)]
    # import random
    ms = []
    positions = set()
    for m in range(M):
        h, w = map(int, input().split())

        positions.add((h, w))
        # h, w = (random.randrange(3*10**5), random.randrange(3*10**5))
        row[h] += 1
        row_set[h].add(w)

        column[w] += 1
        column_set[w].add(h)



    max_rows = set()
    maxR = -1
    for i, v in enumerate(row[1:]):
        if v > maxR:
            max_rows = set()
            max_rows.add(i+1)
            maxR = v
        elif v == maxR:
            max_rows.add(i+1)


    max_cols = set()
    maxC = -1
    for i, v in enumerate(column[1:]):
        if v > maxC:
            max_cols = set()
            max_cols.add(i+1)
            maxC = v
        elif v == maxC:
            max_cols.add(i + 1)


    for y in max_rows:
        for x in max_cols:
            if not (y, x) in positions:
                print(maxR + maxC)
                exit()
    print(maxR + maxC - 1)
main()

Submission status: Accepted

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

h_list = [0 for i in range(H)]
w_list = [0 for i in range(W)]

point = {}
for _ in range(M):
    h, w = map(int, input().split())
    h_list[h - 1] += 1
    w_list[w - 1] += 1
    point[(h - 1, w - 1)] = 1

hmax = 0
wmax = 0
hmap = {}
wmap = {}
for i, h in enumerate(h_list):
    if hmax <= h:
        hmax = h
        hmap.setdefault(h, []).append(i)
for i, w in enumerate(w_list):
    if wmax <= w:
        wmax = w
        wmap.setdefault(w, []).append(i)
# print(hmap)
# print(wmap)
# hmax = max(h_list)
# wmax = max(w_list)
h_index = h_list.index(hmax)
w_index = w_list.index(wmax)

for h in hmap[hmax]:
    for w in wmap[wmax]:
        if (h, w) not in point:
            print(hmax + wmax)
            exit(0)

print(hmax + wmax - 1)

Submission status: Accepted

Solution code:
h,w,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[(0,0)]*n
for i in range(n):
    a,b=map(int,input().split())
    L[i]=(a,b)
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
ans=h_max+w_max
cnt=0
for l in L:
    if H[l[0]-1]==h_max and W[l[1]-1]==w_max:
        cnt+=1
if H.count(h_max)*W.count(w_max)==cnt:
    ans-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

# 各行各列に何個ずつあるか
hs = [0] * h
ws = [0] * w
# 座標を記録
s = set()

readline = sys.stdin.readline
for _ in range(m):
    r, c = [int(i) for i in readline().split()]
    r -= 1
    c -= 1
    hs[r] += 1
    ws[c] += 1
    s.add((r, c))

# 最大値
mh = 0
mw = 0
for i in range(h):
    mh = max(mh, hs[i])
for j in range(w):
    mw = max(mw, ws[j])

# 最大値をとっている行・列
si = []
sj = []
for i in range(h):
    if mh == hs[i]:
        si.append(i)
for j in range(w):
    if mw == ws[j]:
        sj.append(j)

# 爆破対象がないマスに爆弾を設置できれば尚良し。そこでmh+mwをansに仮に記録して、１個でも見つかればその座標を出力。見つからなければ、爆破対象があるマスに爆弾を設置するのが最大となるので、ans=mh+mw-1となる
ans = mh + mw
for i in si:
    for j in sj:
        if (i, j) in s:
            continue
        print(ans)
        exit()
print(ans-1)

Submission status: Accepted

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

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

col_max_indexes = np.where(col == col_max)[0]
row_max_indexes = np.where(row == row_max)[0]

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

print(int(ans))

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import heapq
from bisect import bisect_left,bisect

stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

H,W,M=nm()
r=[0]*(10**6)
c=[0]*(10**6)
mass=set()
for i in range(M):
    h,w=nm()
    mass.add(H*h+w)
    r[h]+=1
    c[w]+=1

rl=[]
cl=[]

r_max=0
for i in range(1,H+1):
    r_max=max(r[i],r_max)
    
c_max=0
for i in range(1,W+1):
    c_max=max(c[i],c_max)

for i in range(1,H+1):
    if(r[i]==r_max):
        rl.append(i)

for i in range(1,W+1):
    if(c[i]==c_max):
        cl.append(i)



for i in rl:
    for j in cl:
        if(i*H+j not in mass):
            print(r_max+c_max)
            sys.exit(0)


print(r_max+c_max-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

col_cnt = [0] * W
row_cnt = [0] * H
col_max = 0
row_max = 0

w2h = defaultdict(list)
h2w = defaultdict(list)
bombs = set()

for _ in range(M):
    h, w = map(lambda x:int(x)-1, input().split())
    row_cnt[h] += 1
    col_cnt[w] += 1
    row_max = max(row_max, row_cnt[h])
    col_max = max(col_max, col_cnt[w])
    bombs.add((h, w))

max_rows = set()
max_cols = set()

for h in range(H):
    if row_cnt[h] == row_max:
        max_rows.add(h)
for w in range(W):
    if col_cnt[w] == col_max:
        max_cols.add(w)

cnt = 0
for h, w in bombs:
    if h in max_rows and w in max_cols:
        cnt += 1

if cnt == len(max_rows) * len(max_cols):
    print(row_max + col_max-1)
else:
    print(row_max + col_max)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
 
hs = [0] * H
ws = [0] * W
boms = set()
 
for i in range(M):
    r,c = map(int, input().split())
    r -= 1
    c -= 1
 
    hs[r] += 1
    ws[c] += 1
    boms.add((r, c))
mh, mw = 0, 0
for i in range(H):
    mh = max(mh, hs[i])
for j in range(W):
    mw = max(mw, ws[j])
max_h_list = []
max_w_list = []
    
for i in range(H):
    if hs[i] == mh: max_h_list.append(i)    
for j in range(W):
    if ws[j] == mw: max_w_list.append(j)
ans = mh + mw
 
for i in max_h_list:
    for j in max_w_list:
        if (i,j) not in boms:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

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

maxh = max(h)
maxw = max(w)
 
listh = {i for i, v in enumerate(h, 1) if v == maxh}
listw = {j for j, v in enumerate(w, 1) if v == maxw}

cnt = len(listh) * len(listw)

for i, j in Mem:
  if i in listh and j in listw:
    cnt -= 1
 
if cnt:
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
item=[list(map(int,input().split())) for i in range(m)]
row=[0]*h
col=[0]*w
for i in range(m):
    x,y=item[i]
    row[x-1]+=1
    col[y-1]+=1
mr,mc=max(row),max(col)
xr=set([i for i in range(h) if row[i]==mr])
xc=set([i for i in range(w) if col[i]==mc])
check=len(xr)*len(xc)
for i in range(m):
    r,c=item[i]
    if r-1 in xr and c-1 in xc:
        check-=1
print(mr+mc if check>0 else mr+mc-1)

Submission status: Accepted

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

hs = [0] * H
ws = [0] * W
checked = set()

for i in range(M):
    r,c = map(int, input().split())
    r -= 1
    c -= 1

    hs[r] += 1
    ws[c] += 1
    checked.add((r, c))

mh, mw = 0, 0
for i in range(H):
    mh = max(mh, hs[i])
for j in range(W):
    mw = max(mw, ws[j])

max_h_list = []
max_w_list = []
    
for i in range(H):
    if hs[i] == mh: max_h_list.append(i)    
for j in range(W):
    if ws[j] == mw: max_w_list.append(j)

ans = mh + mw

for i in max_h_list:
    for j in max_w_list:
        if (i,j) not in checked:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = defaultdict(int)
    count_by_width = defaultdict(int)
    bomb_locations = set()
    for _ in range(target_count):
        h, w = [int(x) - 1 for x in input().split()]
        count_by_height[h] += 1
        count_by_width[w] += 1
        bomb_locations.add((h, w))
    max_h = max(v for v in count_by_height.values())
    max_w = max(v for v in count_by_width.values())
    max_h_rows = [i for i, x in count_by_height.items() if x == max_h]
    max_w_columns = [i for i, x in count_by_width.items() if x == max_w]
    all_crossing_bomb = all((h, w) in bomb_locations
                            for h in max_h_rows for w in max_w_columns)
    return max_h + max_w - all_crossing_bomb


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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

H, W, M = map(int,input().split())
targets = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

cnth = [0] * H
cntw = [0] * W
wlist = [[] for i in range(H)]

for i in range(M):
	hi, wi = targets[i]
	cnth[hi] += 1
	cntw[wi] += 1
	wlist[hi].append(wi)

maxhi = []
maxwi = []
maxh = max(cnth)
maxw = max(cntw)

for i in range(H):
	wlist[i].sort()
	if cnth[i] == maxh:
		maxhi.append(i)
for i in range(W):
	if cntw[i] == maxw:
		maxwi.append(i)

for i in range(len(maxhi)):
	for j in range(len(maxwi)):
		if bisect_right(wlist[maxhi[i]], maxwi[j]) - bisect_left(wlist[maxhi[i]], maxwi[j]) == 0:
			print(maxh + maxw)
			exit()
print(maxh + maxw - 1)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def exists(ite, x):
	return bool(bisect_right(ite, x) - bisect_left(ite, x))

H, W, M = map(int,input().split())
targets = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

cnth = [0] * H
cntw = [0] * W
wlist = [[] for i in range(H)]

for i in range(M):
	hi, wi = targets[i]
	cnth[hi] += 1
	cntw[wi] += 1
	wlist[hi].append(wi)

maxhi = []
maxwi = []
maxh = max(cnth)
maxw = max(cntw)

for i in range(H):
	wlist[i].sort()
	if cnth[i] == maxh:
		maxhi.append(i)
for i in range(W):
	if cntw[i] == maxw:
		maxwi.append(i)

for i in range(len(maxhi)):
	for j in range(len(maxwi)):
		if not exists(wlist[maxhi[i]], maxwi[j]):
			print(maxh + maxw)
			exit()
print(maxh + maxw - 1)

Submission status: Accepted

Solution code:
H, W, M = list(map(int, input().split()))
hrz = [0]*H
vrt = [0]*W
targets = set()
for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    targets.add((h, w))
    hrz[h] += 1
    vrt[w] += 1

hrz_max = max(hrz)
vrt_max = max(vrt)
hrz_max_lines = [i for i in range(H) if hrz[i] == hrz_max]
vrt_max_lines = [i for i in range(W) if vrt[i] == vrt_max]
for h in hrz_max_lines:
    for w in vrt_max_lines:
        if not (h, w) in targets:
            print(hrz_max+vrt_max)
            exit()
print(hrz_max+vrt_max-1)

Submission status: Accepted

Solution code:

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

HSum=[0 for _ in range(H)]
WSum=[0 for _ in range(W)]


bombs = set()
for _ in range(M):
	hi,wi = map(lambda x:int(x)-1,input().split())
	HSum[hi] += 1
	WSum[wi] += 1
	bombs.add( (hi,wi) )
# print(HSum)
# print(WSum)



curMax = 0

## 計算量多すぎ。。
# for h in range(H):
# 	for w in range(W):
# 		tmp = HSum[h] + WSum[w]
# 		if curMax <= tmp:
# 			if (h,w) in bombs:
# 				tmp -= 1
# 			curMax = max( curMax, tmp )

hMax = max(HSum)
wMax = max(WSum)
tmpMax = hMax + wMax

ans = 0

hSumMaxOnly = [h for h, x in enumerate(HSum) if x == hMax]
wSumMaxOnly = [w for w, y in enumerate(WSum) if y == wMax]

for h in hSumMaxOnly:
	if ans == tmpMax:
		break
	for w in wSumMaxOnly:
		if (h,w) in bombs:
			ans = tmpMax - 1
		else:
			ans = tmpMax
			break



print(ans)

Submission status: Accepted

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

h_cnt = [0] * H
w_cnt = [0] * W
hw = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
for h, w in hw:
    h_cnt[h] += 1
    w_cnt[w] += 1

max_h = max(h_cnt)
max_w = max(w_cnt)
hs = [i for i in range(H) if h_cnt[i]==max_h]
ws = [i for i in range(W) if w_cnt[i]==max_w]

ans = max_h+max_w-1
hw = set(hw)
for h in hs:
    for w in ws:
        if (h, w) not in hw:
            print(max_h+max_w)
            exit()
print(max_h+max_w-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
nh=[0]*H
nw=[0]*W
boms=set()
for _ in range(M):
    h,w=map(int,input().split())
    nh[h-1] += 1
    nw[w-1] += 1
    boms.add((h-1, w-1))

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if (i,j) in boms:
            continue
        print(maxh + maxw)
        exit()
print(maxh + maxw - 1)

Submission status: Accepted

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

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

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if (i,j) in boms:
            continue
        print(maxh + maxw)
        exit()
print(maxh + maxw - 1)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
t = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(m)] 
ht = [0]*h
wt = [0]*w
for y,x in t:
  ht[y] += 1
  wt[x] += 1
htm = max(ht)
wtm = max(wt)
htt = [i for i in range(h) if ht[i]==htm]
wtt = [i for i in range(w) if wt[i]==wtm]
ans = htm+wtm-1
t = set(t)
for i in htt:
  for j in wtt:
    if (i,j) not in t:
      print(htm+wtm)
      exit()
print(htm+wtm-1)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

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

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

    # print(row, col, bomb)

    rowmax = max(row)
    colmax = max(col)

    rows = []
    cols = []
    for i in range(H):
        if row[i] == rowmax:
            rows.append(i)
    for i in range(W):
        if col[i] == colmax:
            cols.append(i)

    for r in rows:
        for c in cols:
            if (r, c) in bomb:
                continue
            else:
                print(rowmax + colmax)
                exit()

    print(rowmax + colmax - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoXykgYmVnaW4oXyksIGVuZChfKQojZGVmaW5lIHJhbGwoXykgcmJlZ2luKF8pLCByZW5kKF8pCgppbnQgbWFpbigpIHsKICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICBjaW4udGllKG51bGxwdHIpOwoKICBpbnQgaCwgdywgbTsgY2luID4+IGggPj4gdyA+PiBtOwogIHZlY3RvcjxwYWlyPGludCwgaW50Pj4gaW47CgogIHZlY3RvcjxpbnQ+IGNudF9yb3coaCwgMCksIGNudF9jb2wodywgMCk7CgogIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CiAgICBpbnQgaGgsIHd3OyBjaW4gPj4gaGggPj4gd3c7CiAgICAtLWhoOyAtLXd3OwogICAgaW4uZW1wbGFjZV9iYWNrKGhoLCB3dyk7CiAgICArK2NudF9yb3dbaGhdOyArK2NudF9jb2xbd3ddOwogIH0KCiAgaW50IG14X3JvdyA9ICptYXhfZWxlbWVudChhbGwoY250X3JvdykpOwogIGludCBteF9jb2wgPSAqbWF4X2VsZW1lbnQoYWxsKGNudF9jb2wpKTsKICBpbnQgYW5zID0gbXhfcm93ICsgbXhfY29sOwogIGludDY0IGNhbiA9IGNvdW50KGFsbChjbnRfcm93KSwgbXhfcm93KSAqIGNvdW50KGFsbChjbnRfY29sKSwgbXhfY29sKTsKICBpZiAoY2FuID4gbSkgewogICAgY291dCA8PCBhbnMgPDwgZW5kbDsKICB9IGVsc2UgewogICAgaW50IGJhZCA9IDA7CiAgICBmb3IgKGF1dG8gZSA6IGluKSBiYWQgKz0gKGNudF9yb3dbZS5maXJzdF0gKyBjbnRfY29sW2Uuc2Vjb25kXSA9PSBhbnMpOwogICAgaWYgKGNhbiA+IGJhZCkgewogICAgICBjb3V0IDw8IGFucyA8PCBlbmRsOwogICAgfSBlbHNlIHsKICAgICAgY291dCA8PCBhbnMgLSAxIDw8IGVuZGw7CiAgICB9CiAgfQoKICByZXR1cm4gMDsKfQoiIiIKCndpdGggb3Blbignc29sLmNwcCcsICd3JykgYXMgZjoKICAgIGYud3JpdGUoY29kZSkKCnN1YnByb2Nlc3MuUG9wZW4oWydnKysnLCAnLXN0ZD1jKysxNycsICctTzInLCAnc29sLmNwcCddKS5jb21tdW5pY2F0ZSgpCnN1YnByb2Nlc3MuUG9wZW4oWycuL2Eub3V0J10sIHN0ZGluPXN5cy5zdGRpbiwgc3Rkb3V0PXN5cy5zdGRvdXQpLmNvbW11bmljYXRlKCk='))

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


show_flg=False
show_flg=True

ans=0

for _ in range(1):
    h,w,m=LI()
    b=NLI_(m)
    r=[0]*h
    c=[0]*w
    for x,y in b:
        r[x]+=1
        c[y]+=1
    mr=max(r)
    mc=max(c)
    cnt=0
    for x,y in b:
        if r[x]==mr and c[y]==mc:
            cnt+=1
    ans=mr+mc
    if cnt==r.count(mr)*c.count(mc):
        ans-=1
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0] * H
    ws = [0] * W
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append(tuple([h-1, w-1]))
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    bombs = set(bombs)
    for i in maxhindex:
        for j in maxwindex:
            if (i, j) not in bombs:
                print(ans)
                exit()
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,M=map(int,input().split())
s={tuple(map(lambda x: int(x)-1, input().split())) for i in range(M)}
lh=[0]*H
lw=[0]*W
for i in s:
    lh[i[0]]+=1
    lw[i[1]]+=1
mh=max(lh)
mw=max(lw)
sh=[]
sw=[]
for i in range(H):
    if lh[i]==mh:
        sh.append(i)
for i in range(W):
    if lw[i]==mw:
        sw.append(i)
if len(sh)*len(sw)>M:
    print(mh+mw)
else:
    for i in sh:
        for j in sw:
            if (i,j) not in s:
                print(mh+mw)
                break
        else:
            continue
        break
    else:
        print(mh+mw-1)

Submission status: Accepted

Solution code:
########### E
H, W, M = map(int, input().split())
bombs = []
for _ in range(M):
    bomb = tuple(map(lambda x:int(x)-1, input().split()))
    bombs.append(bomb)

H_list = [0]*H
W_list = [0]*W
for h,w in bombs:
    H_list[h] += 1
    W_list[w] += 1
    
maxX = max(H_list)
maxY = max(W_list)

max_H = [i for i,k in enumerate(H_list) if k == maxX]
max_W = [i for i,k in enumerate(W_list) if k == maxY]

bombs = set(bombs)
for i in max_H:
    for k in max_W:
        if (i,k) not in bombs:
            print(maxX + maxY)
            exit()

print(maxX + maxY -1)

Submission status: Accepted

Solution code:
import sys


H, W, M = map(int, input().split())
bomb =[]
for I in range(M):
    bom = tuple(map(lambda x: int(x) - 1, input().split()))
    bomb.append(bom)
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
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]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
            # 即座に探索を終了する. これによりループの回数は最大でもM+1回となる.
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)