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
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [(0,0) for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = (h-1,w-1)

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

bombers = set(bombers)
for h in h_max_args:
    for w in w_max_args:
        if not (h,w) in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
h_cnt = [0 for _ in range(h)]
w_cnt = [0 for _ in range(w)]
xs = []
ys = []
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    h_cnt[y] += 1
    w_cnt[x] += 1
    xs.append(x)
    ys.append(y)
h_max = max(h_cnt)
w_max = max(w_cnt)
h_max_induce = {i: v for i, v in enumerate(h_cnt) if v == h_max}
w_max_induce = {i: v for i, v in enumerate(w_cnt) if v == w_max}

cnt = 0
for i in range(m):
    x = xs[i]
    y = ys[i]
    if x in w_max_induce and y in h_max_induce:
        cnt += 1
if cnt == len(h_max_induce.keys())*len(w_max_induce.keys()):
    print(h_max+w_max-1)
else:
    print(h_max+w_max)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hw = set(tuple(map(lambda x: int(x) - 1,input().split())) for _ in range(M))

rows = [0] * H
cols = [0] * W
for h, w in hw:
    rows[h] += 1
    cols[w] += 1

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

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

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

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

Submission status: Accepted

Solution code:
H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs ={}
mxx = 0
myy = 0
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1] += 1
    my[y-1] += 1
    mxx = max(mx[x-1], mxx)
    myy = max(my[y-1], myy)
    if y-1 in bs:
        bs[y-1].add(x-1)
    else:
        bs[y-1] = set([x-1])

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1

for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
    else:
        continue
    break

ans = mxx + myy - a
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

h_max = max(h)
w_max = max(w)
h_cnt = h.count(h_max)
w_cnt = w.count(w_max)
ans = h_max + w_max

cnt = 0
for item in item_list:
    if h[item[0]] == h_max and w[item[1]] == w_max:
        cnt += 1

x = h_cnt * w_cnt
if cnt == x:
    ans -= 1

print(ans)

Submission status: Accepted

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

s = [[int(item) -1 for item in input().split()] for _ in range(M)]

# print(s)

col = [0 for _ in range(H)]
row = [0 for _ in range(W)]

bomb_set = set()

# 各列と行で個数を配列
for i,j in s:
    col[i] += 1
    row[j] += 1
    bomb_set.add((i,j))    # 爆弾のある位置

# print(col)
# print(row)
# print(bomb_set)

max_col = max(col)
max_row = max(row)

# 最大の行と列を配列
max_col_index = []
max_row_index = []

# 最大の行を探す
for i in range(H):
    if col[i] == max_col:
        max_col_index.append(i)

# 最大の列を探す
for j in range(W):
    if row[j] == max_row:
        max_row_index.append(j)

# 最大の行と列の組み合わせが爆弾の位置と被っているか確認
for r in max_row_index:
    for c in max_col_index:
        if (c,r) not in bomb_set:
            ans = max_col + max_row
            print(ans)
            sys.exit()

ans = max_col + max_row -1
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    max_s = max(strings)
    max_r = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == max_s:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == max_r:
            rows_max.append(i)
    
    forbidden_positions = set(mapa[strings_max[0]])
    for item in strings_max[1:]:
        forbidden_positions.intersection_update(set(mapa[item]))

    answer_set = set(rows_max).difference(forbidden_positions)
    if answer_set:
        print(max_s + max_r)
    else:
        print(max_s + max_r - 1)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  h, w, m = map(int, input().strip().split())
  fieldh = numpy.zeros(h, dtype=numpy.int)
  fieldw = numpy.zeros(w, dtype=numpy.int)
  field = defaultdict(int)
  for _ in range(m):
    ih, iw = map(int, input().strip().split())
    fieldh[ih-1] += 1
    fieldw[iw-1] += 1
    field[ih-1, iw-1] = 1
    
  max_h = numpy.max(fieldh)
  max_w = numpy.max(fieldw)
  argsort_h = [ ih for ih in range(h) if fieldh[ih] == max_h ]
  argsort_w = [ iw for iw in range(w) if fieldw[iw] == max_w ]
  
  max_cnt = 0
  for ih in argsort_h:
    for iw in argsort_w:
      if field[ih, iw] == 0:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw])
        print(max_cnt)
        return 
      else:
        max_cnt = max(max_cnt, fieldh[ih]+fieldw[iw]-1)
  print(max_cnt)

if __name__=='__main__':
  main()

Submission status: Accepted

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

def main():
    h, w, m = map(int, input().split())
    bomb_row = [0] * h
    bomb_col = [0] * w
    # 座標だけはsetで格納
    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 = [i for i, v in enumerate(bomb_row) if v == bomb_row_max]
    col_index = [i for i, v in enumerate(bomb_col) if v == bomb_col_max]
    ans = bomb_col_max + bomb_row_max
    for row in row_index:
        for col in col_index:
            if (row, col) not in bomb_pos:
                print(ans)
                return
    print(ans-1)
main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    H, W, M = [int(item) for item in input().split()]
    targets = [[int(item) -1 for item in input().split()] for _ in range(M)]

    col = [0 for _ in range(H)]
    row = [0 for _ in range(W)]

    bomb_set = set()
    # 配列で要素を作ると要素数が$10^8$超える場合、setで要素の座標を持っておく


    for i,j in targets:
        col[i] += 1
        row[j] += 1
        bomb_set.add((i,j))

    max_col = max(col)
    max_row = max(row)
    max_col_index = []
    max_row_index = []

    for i in range(H):
        if col[i] == max_col:
            max_col_index.append(i)

    for i in range(W):
        if row[i] == max_row:
            max_row_index.append(i)

    res = 0
    for item in max_col_index:
        for jtem in max_row_index:
            if (item,jtem) not in bomb_set:
                res =max_col + max_row
                break
        else:
            res = max(res, max_col + max_row -1 )
    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

hlist = [0]*H
wlist = [0]*W
sets = set()
for i in range (M):
    h,w = map(lambda x: int(x)-1,input().split())
    hlist[h]+=1
    wlist[w]+=1
    sets.add((h,w))

hmax = 0
hind = []
for i in range(H):
    if hmax < hlist[i]:
        hmax = hlist[i]
        hind = [i]
    elif hmax == hlist[i]:
        hind.append(i)


wmax = 0
wind = []
for i in range(W):
    if wmax < wlist[i]:
        wmax = wlist[i]
        wind = [i]
    elif wmax == wlist[i]:
        wind.append(i)


flag = False
for h in hind:
    for w in wind:
        if (h,w) not in sets:
            flag = True
            break
    if flag:
        break

if flag:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Accepted

Solution code:
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
row.sort(reverse=True)
col.sort(reverse=True)
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: break
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

Submission status: Accepted

Solution code:
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
row.sort(reverse=True)
col.sort(reverse=True)
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: break
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
R = [0] * H
C = [0] * W
B = []
for i in range(M):
    hi, wi = map(lambda s: int(s) - 1, input().split())
    R[hi] += 1
    C[wi] += 1
    B.append((hi, wi))

Rmax = max(R)
Cmax = max(C)
ans = Rmax + Cmax
if R.count(Rmax) * C.count(Cmax) == sum([R[hi] == Rmax and C[wi] == Cmax for hi, wi in B]):
    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hw = []
sh = [0] * H
sw = [0] * W
for i in range(M):
    h, w = map(int, input().split())
    hw.append((h - 1, w - 1))

    sh[h - 1] += 1
    sw[w - 1] += 1

mh = max(sh)
mw = max(sw)

count = 0
for i in range(M):
    if sh[hw[i][0]] == mh and sw[hw[i][1]] == mw:
        count += 1

if sh.count(mh) * sw.count(mw) > count:
    print(mh + mw)
else:
    print(mh + mw - 1)

Submission status: Accepted

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

bomb = []
cnth = [0 for i in range(h)]
cntw = [0 for i in range(w)]
bomh = [set() for i in range(h)]
bomw = [set() for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  cnth[x] += 1
  cntw[y] += 1
  bomh[x].add(y)
  bomw[y].add(x)
  bomb.append([x,y])
maxh = max(cnth)
maxw = max(cntw)
ans = maxh + maxw - 1

xx = []
yy = []
for i in range(h):
  if maxh == cnth[i]:
    xx.append(i)
for i in range(w):
  if maxw == cntw[i]:
    yy.append(i)

for i in xx:
  for j in yy:
    if j not in bomh[i]:
      print (ans+1)
      exit()
print (ans)

Submission status: Accepted

Solution code:
def main():
    H, W, M = map(int, input().split())
    bomb_row = [0 for _ in range(H)]  # 爆弾が何行目に何個あるか
    bomb_column = [0 for _ in range(W)]  # 爆弾が何列目に何個あるか
    bomb_map = set()  # 爆弾がどこにあるか

    for _ in range(M):
        r, c = map(int, input().split())
        bomb_row[r - 1] += 1
        bomb_column[c - 1] += 1
        bomb_map.add((r - 1, c - 1))

    max_row = max(bomb_row)  # 行ごとに見て最も多い爆弾の個数
    max_column = max(bomb_column)  # 列ごとに見て最も多い爆弾の個数
    ans = max_row + max_column

    bomb_max_row = []  # 爆弾がmax_row個ある行
    bomb_max_column = []  # 爆弾がmax_column個ある列

    for i in range(H):
        if bomb_row[i] == max_row:
            bomb_max_row.append(i)
    for i in range(W):
        if bomb_column[i] == max_column:
            bomb_max_column.append(i)

    for r in bomb_max_row:
        for c in bomb_max_column:
            if (r, c) not in bomb_map:  # 最多行と最多列の交点に爆弾が無ければ終了
                print(ans)
                return

    print(ans - 1)  # 最多行と最多列の交点に爆弾があればans - 1


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

h,w,m = readInts()
countx = defaultdict(set)
county = defaultdict(set)
cx,cy = defaultdict(int),defaultdict(int)
for i in range(m):
	x,y = readInts()
	countx[x].add(y)
	county[y].add(x)
	cx[x]+=1
	cy[y]+=1

maxxv = max(cx.values())
maxyv = max(cy.values())
maxxi = [i for i in countx if len(countx[i])==maxxv]
maxyi = [i for i in county if len(county[i])==maxyv]

ans = maxyv+maxxv

for i in maxxi:
	for j in maxyi:
		if j not in countx[i]:
			print(ans)
			exit()

print(ans-1)

Submission status: Accepted

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


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)

Submission status: Accepted

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

tate = [0]*(h+1)
yoko = [0]*(w+1)

basyo = []

for i in range(m):
    hh,ww = map(int,input().split())
    basyo.append((hh-1,ww-1))
    
    tate[hh-1] += 1
    yoko[ww-1] += 1
    
tt,yy = 0,0
x = max(tate)

for i in tate:
    if i == x:
        tt += 1
        
y = max(yoko)
for i in yoko:
    if i == y:
        yy += 1
        
ans = x+y
pl = tt * yy

cur = 0
for i,j in basyo:
    if tate[i] + yoko[j] == ans:
        cur += 1
        
if pl > cur:
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
h , w , m = map(int,input().split())
retu = [0 for i in range(w)]
gyo = [0 for i in range(h)]
basyo = set()
for i in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    retu[b] += 1
    gyo[a] += 1
    basyo.add((a,b))
t = max(retu)
mare = [i for i, v in enumerate(retu) if v == t]
s = max(gyo)
magy = [i for i, v in enumerate(gyo) if v == s]

for i in magy:
    for j in mare:
        if not (i,j) in basyo:
            print(s+t)
            exit()
print(s+t-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[5]:


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


# In[6]:


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)
    ans = 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:
        ans -= 1
    
    return ans


# In[7]:


ans = solve(h,w,m,hw_list)
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
#from random import randint

def f(h,w,m,ins):
    yp = [0]*h
    xp = [0]*w
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = max(yp)
    xpm = max(xp)
    yps = [i for i in range(h) if yp[i] == ypm]
    xps = [i for i in range(w) if xp[i] == xpm]
    ans = ypm+xpm
    for ypsi in yps:
        for xpsi in xps:
            if not (ypsi,xpsi) in s:
                return ans
    return ans-1

if __name__ == "__main__":
    if False:
        while True:
            h,w = randint(1,10**5*3),randint(10**5,10**5*3)
            m = randint(1,min(h*w,10**5*3))
            ins = [(randint(1,h),randint(1,w)) for i in range(m)]
            ans = f(h,w,m,ins)
            print(ans)
    else:
        h,w,m = map(int,input().split())
        ans = f(h,w,m,[list(map(int,input().split())) for i in range(m)])
        print(ans)

Submission status: Accepted

Solution code:
def solve():
    H,W,M = map(int,input().split())
    h_counter = [0] * H
    w_counter = [0] * W

    opponents = []
    for _ in range(M):
        h, w = map(lambda x:int(x)-1, input().split())
        h_counter[h] += 1
        w_counter[w] += 1
        opponents.append((h,w))
    
    h_max = max(h_counter)
    w_max = max(w_counter)

    h_max_area_cnt = 0
    h_max_area_nums = set()
    for h in range(H):
        if h_counter[h] == h_max:
            h_max_area_nums.add(h)
            h_max_area_cnt += 1

    w_max_area_cnt = 0
    w_max_area_nums = set()
    for w in range(W):
        if w_counter[w] == w_max:
            w_max_area_nums.add(w)
            w_max_area_cnt += 1

    max_area_cnt = h_max_area_cnt * w_max_area_cnt

    opponent_in_max_area = 0
    for h,w in opponents:
        if h in h_max_area_nums and w in w_max_area_nums:
            opponent_in_max_area += 1

    if max_area_cnt > opponent_in_max_area:
        print(h_max + w_max)
    else:
        print(h_max + w_max - 1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
s = set([])
H = [0]*(h+1)
W = [0]*(w+1)
for i in range(m):
    x,y = map(int,input().split())
    H[x] += 1
    W[y] += 1
    s.add((x,y))
    
p = [0]*(h+1)
q = [0]*(w+1)
for i in range(h+1):
    p[i] = [i, H[i]]
for i in range(w+1):
    q[i] = [i, W[i]]
    
p.sort(key= lambda val : val[1],reverse=True)
q.sort(key= lambda val : val[1],reverse=True)

mh = max(H)
mw = max(W)
I = H.count(mh)
J = W.count(mw)

sw = 0
for i in range(I):
    if sw == 1:
        break
    for j in range(J):
        if (p[i][0], q[j][0]) in s:
            pass
        else:
            sw = 1
            break

print(mh+mw-1+sw)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,Counter
input = sys.stdin.readline
h,w,m=map(int, input().split())
hs=[]
ws=[]
hw=defaultdict(int)
for i in range(m):
    h0,w0=map(int, input().split())
    hw[(h0,w0)]+=1
    hs.append(h0)
    ws.append(w0)

hd=Counter(hs)
wd=Counter(ws)
hmax=max(hd.values())
wmax=max(wd.values())

max_h_list=[kv[0] for kv in hd.items() if kv[1] == hmax]
max_w_list=[kv[0] for kv in wd.items() if kv[1] == wmax]
ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
h,w=map(list,zip(*[list(map(int,input().split())) for i in range(M)]))
from collections import Counter
hc,wc=Counter(h),Counter(w)
hx,wx=hc.most_common()[0][1],wc.most_common()[0][1]
hl,wl=set([k for k,v in hc.items() if v==hx]),set([k for k,v in wc.items() if v==wx])
x=sum([1 for i in range(M) if h[i] in hl and w[i] in wl])
print(hx+wx if len(hl)*len(wl)-x else hx+wx-1)

Submission status: Accepted

Solution code:
from itertools import product

def zero_origin(s: str) -> int:
  return int(s) - 1

H, W, M = map(int, input().split())
h_obj = [0 for _ in range(H)]
w_obj = [0 for _ in range(W)]
obj = set()
for _ in range(M):
  h, w = map(zero_origin, input().split())
  h_obj[h] += 1
  w_obj[w] += 1
  obj.add((h, w))
max_h = max(h_obj)
max_w = max(w_obj)
h_list = [h for h in range(H) if h_obj[h] == max_h]
w_list = [w for w in range(W) if w_obj[w] == max_w]
for h, w in product(h_list, w_list):
  if (h, w) not in obj:
    print(max_h + max_w)
    break
else:
  print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
#from random import randint
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros(h,dtype=np.int32)
    xp = np.zeros(w,dtype=np.int32)
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = yp.max()
    xpm = xp.max()
    yps = np.where(yp == ypm)[0].tolist()
    xps = np.where(xp == xpm)[0].tolist()
    ans = yp[yps[0]]+xp[xps[0]]
    for ypsi in yps:
        for xpsi in xps:
            if not (ypsi,xpsi) in s:
                return ans
    return ans-1

if __name__ == "__main__":
    if False:
        while True:
            h,w = randint(1,10**5*3),randint(10**5,10**5*3)
            m = randint(1,min(h*w,10**5*3))
            ins = [(randint(1,h),randint(1,w)) for i in range(m)]
            ans = f(h,w,m,ins)
            print(ans)
    else:
        h,w,m = map(int,input().split())
        ans = f(h,w,m,[list(map(int,input().split())) for i in range(m)])
        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

h, w, m = map(int, input().split())
beds = [tuple(map(lambda x: int(x) - 1, input().split()))  for _ in range(m)]

bom_v = Counter(b[0] for b in beds)
bom_h = Counter(b[1] for b in beds)

v_max = max(bom_v.values())
h_max = max(bom_h.values())

cand = list(bom_v.values()).count(v_max) * list(bom_h.values()).count(h_max)
bombs = len([... for i, j in beds if bom_v[i] ==  v_max and bom_h[j] ==  h_max])

if cand - bombs > 0:
    print(v_max + h_max)
else:
    print(v_max + h_max - 1)

Submission status: Accepted

Solution code:
import sys
 
h, w, m = map(int, input().split(' '))
H = [0 for _ in range(h+1)]
W = [0 for _ in range(w+1)]
bomb = set()
for m in range(m):
  i, j = map(int, input().split(' '))
  bomb.add((i, j))
  H[i] += 1
  W[j] += 1
  
max_h = max(H)
max_w = max(W)
target_h = [i for i, v in enumerate(H) if v == max_h]
target_w = [i for i, v in enumerate(W) if v == max_w]
 
for m in target_h:
  for n in target_w:
    if (m, n) not in bomb:
      print(max_h + max_w)
      sys.exit()
	
print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
#from random import randint
import numpy as np


#@njit
def f(h,w,m,ins):
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    #yp[:,1] = np.arange(h)
    #xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = yp[yp.argmax()]
    xpm = xp[xp.argmax()]
    yps = np.where(yp == ypm)[0].tolist()
    xps = np.where(xp == xpm)[0].tolist()
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi]+xp[xpsi]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans = f(h,w,m,ins)
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Accepted

Solution code:
import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h = max(num_in_h)
max_w = max(num_in_w)
max_h_set = set([i for i, v in enumerate(num_in_h) if v == max_h])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max_w])
ans = max_h + max_w - 1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, input().split())
h_list, w_list = [0]*H, [0]*W
check = set()
for _ in range(M):
    h, w = map(int, input().split())
    check.add((h-1, w-1))
    h_list[h-1] += 1
    w_list[w-1] += 1
h_max, w_max = max(h_list), max(w_list)
h_bom = [i for i in range(H) if h_list[i]==h_max]
w_bom = [i for i in range(W) if w_list[i]==w_max]
for h in h_bom:
    for w in w_bom:
        if not (h, w) in check:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)

Submission status: Accepted

Solution code:
import sys
h,w,m = map(int,input().split())
hight = [0]*h
width = [0]*w
S = set()

for i in range(m):
    hi,wi = map(int,input().split())
    S.add((hi-1,wi-1))
    hight[hi-1] += 1
    width[wi-1] += 1

max_vh = max(hight)
max_vw = max(width)

max_h = [i for i in range(h) if hight[i] == max_vh]
max_w = [i for i in range(w) if width[i] == max_vw]
for i in max_h:
    for j in max_w:
        if not(i,j) in S:
            print(max_vh+max_vw)
            sys.exit()

print(max_vh+max_vw-1)

Submission status: Accepted

Solution code:
H,V,M=map(int,input().split())
h=[0 for i in range(M)]
w=[0 for i in range(M)]
for i in range(M):
    h[i],w[i]=map(int,input().split())
Dh=dict()
Dw=dict()
for i in range(M):
    if h[i] in Dh:
        Dh[h[i]]+=1
    else:
        Dh[h[i]]=1
    if w[i] in Dw:
        Dw[w[i]]+=1
    else:
        Dw[w[i]]=1
Hmax=0
Wmax=0
for i in Dh:
    if Dh[i]>Hmax:
        Hmax=Dh[i]
for i in Dw:
    if Dw[i]>Wmax:
        Wmax=Dw[i]
A=0
B=0
for i in Dh:
    if Dh[i]==Hmax:
        A+=1
for i in Dw:
    if Dw[i]==Wmax:
        B+=1
tmp=0
for i in range(M):
    if Dh[h[i]]==Hmax and Dw[w[i]]==Wmax:
        tmp+=1
if A*B>tmp:
    print(Hmax+Wmax)
else:
    print(Hmax+Wmax-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
bomb=[]
h=[0]*H
w=[0]*W
for i in range(M):
    hi,wi=map(int,input().split())
    h[hi-1] += 1
    w[wi-1] += 1
    bomb.append([hi,wi])    
maxh = max(h)
maxw = max(w)
ans = maxh +  maxw
lh=[]
lw=[]
for i in range(len(h)):
    if h[i] == maxh:
        lh.append(i+1)
for i in range(len(w)):
    if w[i] == maxw:
        lw.append(i+1)
a = 0
for i in range(M):
    if ans == h[bomb[i][0]-1]+w[bomb[i][1]-1]:
        a += 1
if a == len(lh)*len(lw):
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
H,W,m = map(int, input().split())

high = [0] * H
width = [0] * W

stone = set()
for i in range(m):
    h, w = map(int,input().split())
    h -= 1
    w -= 1
    
    high[h] += 1
    width[w] += 1
    stone.add((h,w))
    
dic_h = {}
for i in range(len(high)):
    dic_h.setdefault(high[i], [])
    
    dic_h[high[i]].append(i)
    
dic_w = {}
for i in range(len(width)):
    dic_w.setdefault(width[i], [])
    
    dic_w[width[i]].append(i)
    
h_max = max(dic_h.keys())
w_max = max(dic_w.keys())

for i in dic_h[h_max]:
    for j in dic_w[w_max]:
        if (i,j) not in stone:
            print(h_max+w_max)
            sys.exit(0)
            
print(h_max+w_max-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
bombh=[]
bombw=[]
bomb=[]
w=[0]*W
h=[0]*H
for i in range(M):
    hs,ws=map(int,input().split())
    w[ws-1]+=1
    h[hs-1]+=1
    bomb.append([hs-1,ws-1])
maxh=max(h)
maxw=max(w)
ans=maxh+maxw
count=0
for i in range(M):
    if ans==h[bomb[i][0]]+w[bomb[i][1]]:
        count+=1
a=h.count(maxh)*w.count(maxw)
if a==count:
    ans-=1
print(ans)

Submission status: Accepted

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

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

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

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

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

num = len(r_check) * len(c_check)

ans = row_max + col_max - 1
flg = False
if M < num:
    ans += 1
else:
    for r in r_check:
        if flg:
            break
        for c in c_check:
            if not (r, c) in bomb:
                ans += 1
                flg = True
                break

print(ans)

Submission status: Accepted

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

r = max(sum_rows)
c = max(sum_cols)
ans_ = (r + c)
count = 0
for i in range(m):
    if ans_ == (sum_rows[table[i][0]-1]+sum_cols[table[i][1]-1]):
        count += 1

if count == (sum_rows.count(r) * sum_cols.count(c)):
    print(ans_-1)
else:
    print(ans_)

Submission status: Accepted

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

y_list=[0]*h
x_list=[0]*w

for h_i, w_i in hw:
    y_list[h_i-1]+=1
    x_list[w_i-1]+=1

my_cnt=max(y_list)
mx_cnt=max(x_list)

y_cnt=0
x_cnt=0

my_set=set()
mx_set=set()

for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt:
        my_set.add(h_i-1)
    if x_list[w_i-1]==mx_cnt:
        mx_set.add(w_i-1)

cnt=0
for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt and x_list[w_i-1]==mx_cnt:
        cnt+=1

print(my_cnt+mx_cnt-1 if cnt==len(my_set)*len(mx_set) else my_cnt+mx_cnt)