Problem:


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    H,W,M = list(map(int,input().split()))

    counterH = Counter()
    counterW = Counter()
    targets = set()
    for i in range(M):
        h,w = list(map(int,input().split()))
        counterH[h] += 1
        counterW[w] += 1
        targets.add((h,w))

    most_commonH = counterH.most_common()
    most_commonW = counterW.most_common()
    max_w = most_commonW[0][1]
    max_h = most_commonH[0][1]
    if M == 1:
        print(1)
    else:
        ans = 2
        flg = False
        for count_H in most_commonH:
            if max_h != count_H[1]:
                break
            for count_W in most_commonW:
                if max_w != count_W[1]:
                    break
                # print(count_H,count_W)
                if (count_H[0],count_W[0]) in targets:
                    ans = max(ans,count_H[1]+count_W[1]-1)
                else:
                    ans = max(ans,count_H[1]+count_W[1])
                    flg = True
                if flg:
                    break
            if flg:
                break
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline
int1 = lambda x: int(x) - 1

H, W, M = map(int, input().split())
rows, columns = [0] * H, [0] * W
Bomb = set()
for _ in range(M):
    h, w = map(int1, input().split())
    rows[h] += 1
    columns[w] += 1
    Bomb.add((h, w))

r_first = []
r_max = max(rows)
for i, x in enumerate(rows):
    if x == r_max:
        r_first.append(i)

c_first = []
c_max = max(columns)
for i, x in enumerate(columns):
    if x == c_max:
        c_first.append(i)

ans = r_max + c_max - 1
for i, j in itertools.product(r_first, c_first):
    if (i, j) not in Bomb:
        ans = r_max + c_max
        break
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W,M = LI()
    t = [LI() for _ in range(M)]

    hmax = [0] * (H+1)
    wmax = [0] * (W+1)

    for x,y in t:
        hmax[x] += 1
        wmax[y] += 1

    ans = 0

    hm = max(hmax)
    wm = max(wmax)

    xcnt = 0
    ycnt = 0
    for x in range(H+1):
        if hmax[x] == hm:
            xcnt += 1
    for y in range(W+1):
        if wmax[y] == wm:
            ycnt += 1

    cnt = 0
    for x,y in t:
        if hmax[x] == hm and wmax[y] == wm:
            cnt += 1
    if xcnt *  ycnt - cnt:
        print(hm + wm)
    else:
        print(hm+wm-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
Hlist= {}
Wlist ={}
HWlist = []
for i in range(M):
    h,w = map(int,input().split())
    if h not in Hlist:
        Hlist[h] = 1
    else:
        Hlist[h] += 1
    if w not in Wlist:
        Wlist[w] = 1
    else:
        Wlist[w] += 1
    HWlist.append([h,w])
h2 = max([(v,k) for k,v in Hlist.items()])
h = h2[1]
hmax = h2[0]
Dua2 = []
for k,v in Hlist.items():
    if v == hmax:
        Dua2.append(k)
w2 = max([(v,k) for k,v in Wlist.items()])
w = w2[1]
wmax = w2[0]
Dua = []
for k,v in Wlist.items():
    if v == wmax:
        Dua.append(k)
Answer = Hlist[h] + Wlist[w]
Wld = set()
Hld = set()
sign = 0
for i in range(M):
    if HWlist[i][0] == h:
        Wld.add(HWlist[i][1])
for _ in range(len(Dua)):
    if Dua[_] not in Wld:
        break
    elif _ == len(Dua)-1:
        sign -= 1
for i in range(M):
    if HWlist[i][1] == w:
        Hld.add(HWlist[i][0])
for _ in range(len(Dua2)):
    if Dua2[_] not in Hld:
        break
    elif _ == len(Dua2)-1:
        sign -= 1
if sign == -2:
    Answer -= 1
print(Answer)

Submission status: Accepted

Solution code:
from sys import exit

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

r = [0] * H
c = [0] * W
l = []
for _ in range(M):
    h, w = map(int, input().split())
    l.append([h-1, w-1])
    r[h-1] += 1
    c[w-1] += 1

set_r = set()
set_c = set()
max_r, max_c = max(r), max(c)

for i in range(H):
    if r[i] == max_r:
        set_r.add(i)

for i in range(W):
    if c[i] == max_c:
        set_c.add(i)

cnt = 0
for x, y in l:
    if x in set_r and y in set_c:
        cnt += 1

if cnt == len(set_r) * len(set_c):
    print(max_r + max_c - 1)
else:
    print(max_r + max_c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
H,W,M=f()
g=[set() for _ in range(H)]
ch=[0]*H
cw=[0]*W
for _ in range(M):
  h,w=f()
  g[h-1].add(w-1)
  ch[h-1]+=1
  cw[w-1]+=1
mh=max(ch)
mw=max(cw)
lh=[i for i in range(H) if ch[i]==mh]
lw=[i for i in range(W) if cw[i]==mw]
c=mh+mw
for i in lh:
  if len(g[i])<1: exit(print(c))
  for j in lw:
    if j not in g[i]: exit(print(c))
print(c-1)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

h = [-1]
w = [-1]
hw_dict = defaultdict(int)
for _ in range(M):
    hi, wi = map(int, input().split())
    h.append(hi)
    w.append(wi)
    hw_dict[(hi, wi)] = 1
# print(h)
# print(w)
# print(hw)
h_cnt = [0] * (H + 1)
w_cnt = [0] * (W + 1)
for i in range(1, M + 1):
    h_cnt[h[i]] += 1
    w_cnt[w[i]] += 1
# print(h_cnt)
# print(w_cnt)

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []


for i in range(1, H + 1):
    if h_cnt[i] == h_max:
        h_max_idx.append(i)

for i in range(1, W + 1):
    if w_cnt[i] == w_max:
        w_max_idx.append(i)


# print(h_max_idx)
# print(w_max_idx)

ans = 0

for i in h_max_idx:
    for j in w_max_idx:
        tmp = h_cnt[i] + w_cnt[j]
        if hw_dict[(i, j)] == 1:
            tmp -= 1
            ans = max(ans, tmp)
        else:
            ans = tmp
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
row=defaultdict(int)
col=defaultdict(int)
H,W,M=map(int,input().split())
#matrix=[[1 for i in range(W)] for j in range(H)]
matrix=defaultdict(bool)
for i in range(M):
    h,w=map(int,input().split())
    row[h-1]+=1
    col[w-1]+=1
    matrix[(h-1,w-1)]=True
#print(row)
#print(col)
#for i in matrix:
#    print(*i)
temp=list(row.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt=0
for i in range(W):
    temp=0
    if matrix[(a,i)]:
        temp=(b+col[i]-1)
    else:
        temp=(b+col[i])
    cnt=max(cnt,temp)
#print(cnt)
temp=list(col.items())
temp.sort(key=lambda x:x[1])
a,b=temp[-1][0],temp[-1][1]
cnt2=0
for i in range(H):
    temp=0
    if matrix[(i,a)]:
        temp=(b+row[i]-1)
    else:
        temp=(b+row[i])
    cnt2=max(cnt2,temp)
print(max(cnt,cnt2))

Submission status: Accepted

Solution code:
H, W, M = map(int,input().rstrip().split())
bomb = []
r = [0]*H
c = [0]*W
max_r = 0
max_c = 0
r_i = []
c_j = []
r_num = 0
c_num = 0
for i in range(M):
    h, w = map(int,input().rstrip().split())
    bomb.append([h-1,w-1])
    r[h-1] += 1
    if r[h-1]>max_r:
        max_r = r[h-1]
        r_i = [h-1]
        r_num = 1
    elif r[h-1]==max_r:
        r_i.append(h-1)
        r_num += 1
    c[w-1] += 1
    if c[w-1]>max_c:
        max_c = c[w-1]
        c_j = [w-1]
        c_num = 1
    elif c[w-1]==max_c:
        c_j.append(w-1)
        c_num += 1
r_set = set(r_i)
c_set = set(c_j)
num = 0
for i in range(M):
    if bomb[i][0] in r_set:
        if bomb[i][1] in c_set:
            num += 1
if num<r_num*c_num:
    ans = max_r+max_c
else:
    ans = max_r+max_c-1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
inpl = lambda: list(map(int,input().split()))
H, W, M = inpl()
Shw = set()
Sh = []
Sw = []
for _ in range(M):
    h, w = inpl()
    h -= 1
    w -= 1
    Sh.append(h)
    Sw.append(w)
    Shw.add((h,w))

Gh = Counter(Sh).most_common()
Gw = Counter(Sw).most_common()
mh = Gh[0][1]
mw = Gw[0][1]
Lh = len(Gh)
Lw = len(Gw)
i = j = 0
while i < Lh and Gh[i][1] == mh:
    j = 0
    while j < Lw and Gw[j][1] == mw:
        if not (Gh[i][0],Gw[j][0]) in Shw:
            ans = mh + mw
            break
        j += 1
    else:
        i += 1
        continue
    break
else:
    ans = mh + mw - 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.readline

def main():
    H, W, M = map(int, input().split())
    d = defaultdict(int)
    e = defaultdict(int)
    x = defaultdict(set)
    y = defaultdict(set)
    X = []
    for _ in range(M):
        h, w = map(int, input().split())
        d[h] += 1
        e[w] += 1
        x[h].add(w)
        y[w].add(h)
        
    a = max(d.values())
    b = max(e.values())
    cand_d = set()
    cand_e = set()
    for i, j in d.items():
        if j == a:
            cand_d.add(i)

    for i, j in e.items():
        if j == b:
            cand_e.add(i)

    for i in cand_d:
        if (cand_e - x[i]) != set():
            ans = a + b
            print(ans)
            exit()

    for i in cand_e:
        if (cand_d - y[i]) != set():
            ans = a + b
            print(ans)
            exit()

    print(a + b - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

#import numpy as np
#from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


H, W, M = acinput()

Bh = [[0, i] for i in range(H+1)]
Bw = [[0, i] for i in range(W+1)]
B = {}
for i in range(M):
    h, w = acinput()
    Bh[h][0] += 1
    Bw[w][0] += 1
    B[(h, w)] = 1

Bh = sorted(Bh,  reverse=True)
Bw = sorted(Bw,  reverse=True)

Hidx = []
Widx = []
k = 0
while True:
    Hidx.append(k)
    if Bh[k][0] > Bh[k+1][0]:
        break
    k += 1
    if k >= len(Bw):
        break

k = 0
while True:
    Widx.append(k)
    if Bw[k][0] > Bw[k+1][0]:
        break
    k += 1
    if k >= len(Bw):
        break

""" print(Bh)
print(Hidx)
print(Bw)
print(Widx) """

for hi in Hidx:
    h = Bh[hi][1]
    for wi in Widx:
        w = Bw[wi][1]
        if not((h, w) in B):
            res = Bh[0][0]+Bw[0][0]
            print(res)
            #print(h, w)
            sys.exit()


print(Bh[0][0]+Bw[0][0]-1)

# print("cross")

'''
h=0
w=0
while True:
    if not((h, w) in B) or Bh[h] > Bh[h + 1] or Bw[w] > Bw[w + 1]:
        res=Bh[h]+Bw[w]+a
        break

    res=Bh[h]+Bw[w]+1
    
'''

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
countH = [[h, 0] for h in range(H)]
countW = [[w, 0] for w in range(W)]
Bh = {}

for i in range(M):
  h, w = map(int, input().split())
  h, w = h-1, w-1
  if h in Bh:
    Bh[h].add(w)
  else:
    Bh[h] = {w}
  countH[h][1] += 1
  countW[w][1] += 1

countH.sort(reverse=True, key=lambda x: x[1])
countW.sort(reverse=True, key=lambda x: x[1])
#print(countH)
#print(countW)
#rint(Bh)

maxh = countH[0][1]
maxw = countW[0][1]
ans = maxh + maxw
ch = [countH[0][0]]
i = 1
while i < H and countH[i][1]==maxh:
  ch.append(countH[i][0])
  i += 1
cw = [countW[0][0]]
i = 1
while i < W and countW[i][1]==maxw:
  cw.append(countW[i][0])
  i += 1
flag = False
for h in ch:
  for w in cw:
    #print(h,w)
    if w not in Bh[h]:
      flag = True
      break
if flag:
  print(ans)
else:
  print(ans-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
h,w,m = map(int,input().split())
y_dic = defaultdict(int)
x_dic = defaultdict(int)
bom_dic = set()
for _ in range(m):
    y,x = map(int,input().split())
    y_dic[y]+=1
    x_dic[x]+=1
    bom_dic.add((y,x))
y_max = max(y_dic.values())
x_max = max(x_dic.values())
y_max_indexes = [key for key,value in y_dic.items() if value==y_max]
x_max_indexes = [key for key,value in x_dic.items() if value==x_max]
for y_index in y_max_indexes:
    for x_index in x_max_indexes:
        if (y_index,x_index) not in bom_dic:
            print(y_max+x_max)
            exit()
            
print(y_max+x_max-1)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,M=mi()

    H_count = [0] * (H+1)
    W_count = [0] * (W+1)
    G = set()
    seenH = set()
    seenW = set()
    for i in range(M):
        h,w=mi()
        H_count[h] += 1
        W_count[w] += 1

        seenH.add(h)
        seenW.add(w)
        G.add((h,w))
    
    Hs = []
    Ws = []
    for i in range(max(H,W)+1):
        if i < len(H_count):
            count = H_count[i]
            if count > 0:
                Hs.append((count,i))

        if i < len(W_count):
            count = W_count[i]
            if count > 0:
                Ws.append((count,i))


    Hs.sort(reverse=True)
    Ws.sort(reverse=True)

    # print(Hs)
    # print(Ws)

    h_count,h = Hs[0]
    w_count,w = Ws[0]

    original = h_count + w_count
    ans = original
    if (h,w) in G:
        # print("a")
        ans -= 1

        i = 1
        sameH = []
        while i < len(Hs) and Hs[i][0] == h_count:
            # print("h")
            h = Hs[i][1]
            i += 1
            sameH.append(h)
        
        i = 1
        sameW = []    
        while i < len(Ws) and Ws[i][0] == w_count:
            w = Ws[i][1]
            i += 1
            sameW.append(w)
           
        max_mass = (len(sameH)+1) * (len(sameW)+1)

        # print(max_mass)
        on_bom_count = 0
        for h,w in G:
            count = H_count[h] + W_count[w]
            if count == original:
                on_bom_count += 1
        
        if max_mass - on_bom_count > 0:
            ans += 1

                
    print(ans)


        
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W, M= getNM()
query = [getList() for i in range(M)]
bomb_dict = defaultdict(set)

# 縦hに行くとi個飴がもらえる
h_list = defaultdict(int)
w_list = defaultdict(int)
h_len = set()
w_len = set()

for h, w in query:
    h -= 1
    w -= 1
    h_list[h] += 1
    w_list[w] += 1
    h_len.add(h)
    w_len.add(w)
    bomb_dict[h].add(w)

# 飴がj個もらえる行はどこか
candy_h = defaultdict(list)
candy_w = defaultdict(list)

for i in h_list.items():
    candy_h[i[1]].append(i[0])
for i in w_list.items():
    candy_w[i[1]].append(i[0])

opt_h = sorted(candy_h.items(), reverse = True)[0]
opt_w = sorted(candy_w.items(), reverse = True)[0]
h_n = opt_h[0]
w_n = opt_w[0]

flag = False
ser_h = opt_h[1]
ser_w = opt_w[1]

for i in ser_h:
    for j in ser_w:
        # ボンバーマンh列に一つもなければ
        if not j in bomb_dict[i]:
            print(h_n + w_n)
            exit()

print(h_n + w_n - 1)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
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 TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	h,w,m=MI()
	A=[0]*(h+1)
	B=[0]*(w+1)
	C=[[] for _ in range(h+1)]

	for _ in range(m):
		hh,ww=MI()
		A[hh]+=1
		B[ww]+=1
		C[hh].append(ww)


	for i in range(h+1):
		C[i].sort()

	AA=max(A)
	BB=max(B)

	x=[]
	y=[]

	for i,v in enumerate(A):
		if v==AA:
			x.append(i)

	for i,v in enumerate(B):
		if v==BB:
			y.append(i)

	#print(x,y,AA,BB)
	#print(C)
	ans=0

	for i in x:
		C[i].append(10**7)
		#print("a")
		#print(C[i])
		#print(y)
		a=0
		for j in y:
			while a<len(C[i]):
				if j==C[i][a]:
					a+=1
					break
				elif j<C[i][a]:
					print(AA+BB)
					exit()
				else:
					a+=1

	print(AA+BB-1)
















if __name__ == "__main__":
	main()

Submission status: Accepted

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

X=[0]*(H+1)
Y=[0]*(W+1)

B=set()
for _ in range(M):
    x,y=map(int,input().split())
    B.add((x,y))
    X[x]+=1
    Y[y]+=1

x_max=max(list(range(1,H+1)),key=lambda x:X[x])
P=X[x_max]
Alpha=[x for x in range(1,H+1) if X[x]==P]

y_max=max(list(range(1,W+1)),key=lambda x:Y[x])
Q=Y[y_max]
Beta=[y for y in range(1,W+1) if Y[y]==Q]


if len(Alpha)*len(Beta)<=M:
    Flag=False
    for p in Alpha:
        for q in Beta:
            if (p,q) not in B:
                Flag=True
                break
        if Flag:
            break
else:
    Flag=True

print(P+Q-(not Flag))


assert 1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


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

h_cnt = np.zeros(h, dtype=int)
w_cnt = np.zeros(w, dtype=int)
bom_cord = set()
for i in range(m):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    bom_cord.add((hi, wi))
    h_cnt[hi] += 1
    w_cnt[wi] += 1

w_max = w_cnt.max()

h_argsort = h_cnt.argsort()[::-1]
w_argsort = w_cnt.argsort()[::-1]

bomber = 0
for hi in h_argsort:
    if h_cnt[hi] + w_max <= bomber:
        break
    
    for wi in w_argsort:
        if h_cnt[hi] + w_cnt[wi] <= bomber:
            break

        if (hi, wi) in bom_cord:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi] - 1)
        else:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi])

print(bomber)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))


H,W,M=map(int, input().split())
#P = [list(map(int,input().split())) for i in range(M)]
Hlist=[0] * M
Wlist=[0] * M
P = []
for i in range(M):
    Hlist[i],Wlist[i]=map(int, input().split())
    P.append([Hlist[i],Wlist[i]])

Pset = set(map(tuple, P))

HC = Counter(Hlist)
HD = HC.most_common()
WC = Counter(Wlist)
WD = WC.most_common()

Hmax = HD[0][1]
Wmax = WD[0][1]
ans = Hmax + Wmax

# print(P)
# print(Pset)
# print("H----")
# print(Hlist)
# print(HC)
# print(HD)
# print("Hmax=",Hmax)
# print("W----")
# print(Wlist)
# print(WC)
# print(WD)
# print("Wmax=",Wmax)

# print(ans)


for i in range(len(HD)):
    if HD[i][1] != Hmax:
        break
    for j in range(len(WD)):
        if WD[j][1] != Wmax:
            break
        tmp = tuple([HD[i][0],WD[j][0]])
        if (tmp in Pset) == False:
            print(ans)
            sys.exit()
        
print(ans-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
r = [0]*h
c = [0]*w
s = set()
for i in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    r[hi] += 1
    c[wi] += 1
    s.add((hi, wi))

a = max(r)
b = max(c)

p = []
q = []
for i in range(h):
    if r[i] == a:
        p.append(i)
for j in range(w):
    if c[j] == b:
        q.append(j)

k = 1
for i in p:
    for j in q:
        if (i, j) not in s:
            k = 0
            break
    if k == 0:
        break

print(a + b - k)

Submission status: Accepted

Solution code:
from collections import Counter
h, w, m = map(int, input().split())
A = []
B = []
points = set()
for _ in range(m):
    a, b = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    points.add((a - 1, b - 1))
ac = Counter(A).most_common()
bc = Counter(B).most_common()
#print(ac, bc, points)

x = ac[0][1]
y = bc[0][1]

acm = []
bcm = []

for i, j in ac:
    if j == x:
        acm.append(i)
    else:
        break

for i, j in bc:
    if j == y:
        bcm.append(i)
    else:
        break

ans = x + y - 1
for i in acm:
    for j in bcm:
        if (i, j) not in points:
            print(ans + 1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    h, w, m = _ia()
    hh = [0] * h
    ww = [0] * w
    f = {}
    for _ in range(m):
        i, j = map(lambda x: x-1, _ia())
        hh[i] += 1
        ww[j] += 1
        f[(i, j)] = 1

    lh = []
    mh = max(hh)
    for i, hi in filter(lambda x: x[1] == mh, enumerate(hh)):
        lh.append(i)

    lw = []
    mw = max(ww)
    for i, wi in filter(lambda x: x[1] == mw, enumerate(ww)):
        lw.append(i)

    ans = mh + mw
    for li in lh:
        for wi in lw:
            if f.get((li, wi), 0) == 0:
                return ans
    return ans - 1


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

Submission status: Accepted

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

HD=defaultdict(int)
WD=defaultdict(int)
for h,w in bombs:
    HD[h]+=1
    WD[w]+=1

HMAX=max(HD.values())
WMAX=max(WD.values())
ans_min=HMAX+WMAX-1

h_cand=set()
w_cand=set()
for h in range(H):
    if HD[h]==HMAX:
        h_cand.add(h)

for w in range(W):
    if WD[w]==WMAX:
        w_cand.add(w)

for h in h_cand:
    for w in w_cand:
        if (h,w) not in bombs:
            print(ans_min+1)
            exit()
print(ans_min)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

h,w,m = map(int,readline().split())
inp = [list(map(int,readline().split())) for i in range(m)]

x = [0] * h
y = [0] * w

for i in range(m):
    inp[i][0] -= 1
    inp[i][1] -= 1

for xi,yi in inp:
    x[xi] += 1
    y[yi] += 1

ansx = max(x)
idx = []
for i,xi in enumerate(x):
    if xi == ansx:
        idx.append(i)

ansy = max(y)
idy = []
for i,yi in enumerate(y):
    if yi == ansy:
        idy.append(i)

s = set()

for xi,yi in inp:
    s.add(xi*1000000+yi)
#print(s)

for xx in idx:
    for yy in idy:
        if xx*1000000+yy not in s:
            print(ansx+ansy)
            exit()
print(ansx+ansy-1)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
H = [set() for _ in range(h)]
W = [set() for _ in range(w)]
cord = []
for _ in range(m):
    a,b = map(int,input().split())
    H[a-1].add(b-1)
    W[b-1].add(a-1)
    cord.append((a-1,b-1))
X = 0
set_x = set()
for i in range(h):
    if X<len(H[i]):
        X = len(H[i])
        set_x= set()
        set_x.add(i)
    elif X ==len(H[i]):
        set_x.add(i)

    
Y = 0
set_y = set()
for i in range(w):
    if Y<len(W[i]):
        Y = len(W[i])
        set_y = set()
        set_y.add(i)
    elif Y ==len(W[i]):
        set_y.add(i)
# print(set_x,set_y,X,Y)
n = len(set_x)*len(set_y)
for x,y in cord:
    if x in set_x and y in set_y:
        n -=1
if n:
    cnt =0
else:
    cnt = -1

print(X+Y+cnt)

Submission status: Accepted

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

h, w, m = map(int, input().split())
dic_h = {}
dic_w = {}
s = set([])
for _ in range(m):
    i, j = map(int, input().split())
    s.add((i, j))
    try:
        dic_h[i] += 1
    except:
        dic_h[i] = 1
    try:
        dic_w[j] += 1
    except:
        dic_w[j] = 1

max_h = 0
lh = []
max_w = 0
lw = []
for i, j in dic_h.items():
    if max_h < j:
        max_h = j
        lh = [i]
    elif max_h == j:
        lh.append(i)
for i, j in dic_w.items():
    if max_w < j:
        max_w = j
        lw = [i]
    elif max_w == j:
        lw.append(i)

for i in lh:
    for j in lw:
        if (i, j) not in s:
            print(max_h + max_w)
            exit()
print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
tate = defaultdict(int)
yoko = defaultdict(int)
T = {}
for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1]+= 1
    T[(h-1, w-1)] = 1

tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_m = tate[0][1]
yoko_m = yoko[0][1]
ans = 0
for i in range(len(tate)):
    if ans == tate_m + yoko_m:
        break
    if tate[i][1] == tate_m:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 1)
                else:
                    ans = max(ans, tate_m + yoko_m)
            else:
                break
    else:
        break
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:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w,m=mdata()
bombh=[0]*h
bombw=[0]*w
s=set()
for i in range(m):
    x,y=mdata()
    x-=1
    y-=1
    s.add((x,y))
    bombh[x]+=1
    bombw[y]+=1
cnt=0
mh=max(bombh)
mw=max(bombw)
for (i,j) in s:
    if bombh[i]==mh and bombw[j]==mw:
        cnt+=1
k=0
for i in range(h):
    if bombh[i]==mh:
        k+=1
for i in range(w):
    if bombw[i]==mw:
        cnt-=k
if cnt==0:
    out(mh+mw-1)
else:
    out(mh+mw)

Submission status: Accepted

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

hlist=[0]*H
wlist=[0]*W
hwset=set()
for _ in range(M):
  h,w=map(int,input().split())
  hlist[h-1]+=1
  wlist[w-1]+=1
  hwset.add((h-1,w-1))
  
hmax=max(hlist)
wmax=max(wlist)

hlist2=[]
for i in range(H):
  if hlist[i]==hmax:
    hlist2.append(i)
hlist2.sort(reverse=True)
random.shuffle(hlist2)

wlist2=[]
for i in range(W):
  if wlist[i]==wmax:
    wlist2.append(i)
wlist2.sort(reverse=True)
random.shuffle(wlist2)

#print(hlist2,wlist2)
H2=len(hlist2)
W2=len(wlist2)

if H2*W2>=10**7:
  norm=(H2*W2)//(10**7)
  H2=int(H2/(norm**0.5))
  W2=int(W2/(norm**0.5))

for i in range(H2):
  ii=hlist2[i]
  for j in range(W2):
    jj=wlist2[j]
    if not (ii,jj) in hwset:
      print(hmax+wmax)
      sys.exit(0)
else:
  print(hmax+wmax-1)

Submission status: Accepted

Solution code:
from itertools import product
H,W,M = map(int,input().split())
h_list = [0] * M
w_list = [0] * M
for m in range(M):
    h_list[m],w_list[m] = map(int,input().split())
hh_list = [0] * H
ww_list = [0] * W
for m in range(M):
    hh_list[h_list[m]-1] += 1
for m in range(M):
    ww_list[w_list[m]-1] += 1
h_max = max(hh_list)
w_max = max(ww_list)

h_ans = []
w_ans = []

for hh in range(H):
    if hh_list[hh] == h_max:
        h_ans.append(hh)
for ww in range(W):
    if ww_list[ww] == w_max:
        w_ans.append(ww)
cnt = 0
h_set = set(h_ans)
w_set = set(w_ans)
for i,j in zip(h_list,w_list):
    if i-1 in h_set and j-1 in w_set:
        cnt += 1
if cnt == len(h_ans) * len(w_ans):
    print(h_max + w_max - 1)
else:
    print(h_max + w_max)

Submission status: Accepted

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

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

h = [0] * H
w = [0] * W
bomb = set([])

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

max_h = max(h)
max_w = max(w)

h_ind = []
w_ind = []


# print(h)
# print(w)


for i, mh in enumerate(h):
    if mh == max_h:
        h_ind.append(i)

for i, mw in enumerate(w):
    if mw == max_w:
        w_ind.append(i)

# print(h_ind)
# print(w_ind)

for ih in h_ind:
    for iw in w_ind:
        if (ih, iw) not in bomb:
            print(max_h + max_w)
            exit()

print(max_h + max_w - 1)