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
def input(): return sys.stdin.readline().rstrip()


def main():
    H,W,m=map(int, input().split())
    Hline=[]
    wline=[]
    blist=dict()
    for k in range(m):
        h,w=map(int, input().split())
        Hline.append(h)
        wline.append(w)
        blist[h*(W+2)+w]=0
    hc=Counter(Hline).most_common()
    wc=Counter(wline).most_common()
    ans=hc[0][1]+wc[0][1]
    hl=[]
    wl=[]
    for hcc in hc:
        if hcc[1]!= hc[0][1]:
            break
        hl.append(hcc[0])
    for wcc in wc:
        if wcc[1]!= wc[0][1]:
            break
        wl.append(wcc[0])
    for hll in hl:
        for wll in wl:
            if hll*(W+2)+wll not in blist:
                print(ans)
                exit()
    print(ans-1)

    
        



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,M=map(int, input().split())
nrow=[0]*H
ncol=[0]*W
xycoord=[]

for _ in range(M):
	h,w=map(int, input().split())
	nrow[h-1]+=1
	ncol[w-1]+=1
	xycoord+=[[w-1,h-1]]

#ncol=collections.Counter(xcoord)
#nrow=collections.Counter(ycoord)

a=max(nrow)
b=max(ncol)
row_cand=set([i for i, x in enumerate(nrow) if x == a])
col_cand=set([i for i, x in enumerate(ncol) if x == b])


flag=0
for i in xycoord:
	if (i[0] in col_cand) and (i[1] in row_cand):
		flag+=1

if flag<(len(col_cand)*len(row_cand)):
	print(max(nrow)+max(ncol))
else:
	print(max(nrow)+max(ncol)-1)



# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
T = [0] * M
H_cnt = {}
W_cnt = {}
HW = {}
for i in range(M):
    h,w = map(int,input().split())
    if not h in H_cnt:
        H_cnt[h] = 0
    if not w in W_cnt:
        W_cnt[w] = 0
    H_cnt[h] += 1
    W_cnt[w] += 1
    HW[(h,w)] = 1

HL = [[h,cnt] for h,cnt in H_cnt.items()]
WL = [[w,cnt] for w,cnt in W_cnt.items()]

HL.sort(key=lambda x: x[1],reverse=True)
WL.sort(key=lambda x: x[1],reverse=True)

HS = {}
max_cnth = 0
for h,cnt in HL:
    if max_cnth<=cnt:
        HS[h] = cnt
        max_cnth = max(max_cnth,cnt)
        continue
    break

WS = {}
max_cntw = 0
for w,cnt in WL:
    if max_cntw<=cnt:
        WS[w] = cnt
        max_cntw = max(max_cntw,cnt)
        continue
    break

cnt = 0
ans = 0

# ここの判定を高速にする
cross_cnt = 0
for hw in HW.keys():
    h,w = hw
    if h in HS and w in WS:
        cross_cnt+=1
if len(WS) * len(HS)==cross_cnt:
    print(max_cnth+max_cntw-1)
    exit()
print(max_cnth+max_cntw)


#for h,hcnt in HS:
#    for w,wcnt in WS:
#        if (h,w) in HW:
#            cnt = hcnt+wcnt-1
#            ans = max(ans,cnt)
#            continue
#        cnt = hcnt+wcnt
#        ans = max(ans,cnt)

Submission status: Accepted

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

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(ws) < len(hs):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break
        
else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)

Submission status: Accepted

Solution code:
import bisect
h,w,m=map(int,input().split())
xnum=[[0,i] for i in range(h)]
ynum=[[0,i] for i in range(w)]
hw=[]
xmax=[]
ymax=[]
for i in range(m):
  s,t=map(int,input().split())
  xnum[s-1][0]+=1
  ynum[t-1][0]+=1
  hw.append([s-1,t-1])
hw.sort()
xnum.sort()
ynum.sort()
xmax.append(xnum[-1][1])
ymax.append(ynum[-1][1])
for i in range(2,len(xnum)+1):
  if xnum[-1*i][0]==xnum[-1][0]:
    xmax.append(xnum[-1*i][1])
  else:
    break
for i in range(2,len(ynum)+1):
  if ynum[-1*i][0]==ynum[-1][0]:
    ymax.append(ynum[-1*i][1])
  else:
    break
flag=True
for i in xmax:
  for j in ymax:
    l=bisect.bisect_left(hw,[i,j])
    r=bisect.bisect_right(hw,[i,j])
    if [i,j] in hw[l:r]:
      continue
    else:
      flag=False
      break

if flag:
  ans=xnum[-1][0]+ynum[-1][0]-1
else:
  ans=xnum[-1][0]+ynum[-1][0]
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

H,W,M=map(int,input().split())
AB=[tuple(map(int,input().split()))for i in range(M)]
AB=[(a-1,b-1)for a,b in AB]
st=set(AB)

Wc=defaultdict(lambda :0)
Hc=defaultdict(lambda :0)
for a,b in AB:
    Hc[a]+=1
    Wc[b]+=1

Hm=max(Hc.values())
hhh=list(Hc.keys())
www=list(Wc.keys())
for i in hhh:
    if Hc[i]!=Hm:
        Hc.pop(i)
Wm=max(Wc.values())
for j in www:
    if Wc[j]!=Wm:
        Wc.pop(j)

ans=0
count=0
for i in Hc.keys():
    for j in Wc.keys():
        add = -1 if (i,j) in st else 0
        tmp= Hc[i] + Wc[j] + add
        ans=max(ans,tmp)
        if count>300000:
            break
        count+=1

print(ans)

Submission status: Accepted

Solution code:
h, w, m = (int(x) for x in input().split())
bomb = {}
bomb_h = [0]*h
bomb_w = [0]*w
for i in range(m):
    hm, wm = (int(x) for x in input().split())
    hm-=1
    wm-=1
    bomb[(hm, wm)] = 0
    bomb_h[hm]+=1
    bomb_w[wm]+=1
h_kouho = []
w_kouho = []
h_max = max(bomb_h)
w_max = max(bomb_w)
for i in range(h):
    if bomb_h[i]==h_max:
        h_kouho.append(i)
for i in range(w):
    if bomb_w[i]==w_max:
        w_kouho.append(i)
boo = False
for i in h_kouho:
    for j in w_kouho:
        if (i, j) not in bomb:
            boo=True
            break
    else:
        continue
    break
if boo:
    print(h_max+w_max)
else:
    print(h_max+w_max-1)

Submission status: Accepted

Solution code:
## coding: UTF-8
#memo:重なっている位置に爆弾があるかないかで、1こ増減することが考えられる
#import numpy as np

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

tate = [0] * H
yoko = [0] * W


bomb = set()
for i in range(M):
    hi, wi = map(int,input().split())
    tate[hi-1] += 1
    yoko[wi-1] += 1
    bomb.add((hi,wi))
    

#print(tate)
#print(yoko)
#print(bomb)
'''
tate_max = max(tate)
yoko_max = max(yoko)
index_tate = [i for i, v in enumerate(tate) if v == tate_max]
index_yoko = [i for i, v in enumerate(yoko) if v == yoko_max]
'''
tate_max = 0
index_tate = []
for i, v in enumerate(tate):
    if(tate_max < v):
        tate_max = v
        index_tate = [i]
    elif(tate_max == v):
        index_tate.append(i)
#print(tate_max, index_tate)

yoko_max = 0
index_yoko = []
for i, v in enumerate(yoko):
    if(yoko_max < v):
        yoko_max = v
        index_yoko = [i]
    elif(yoko_max == v):
        index_yoko.append(i)
#print(yoko_max, index_yoko)


#print(index_tate, index_yoko)

dammy = True
#1子でも「そこにない」ものがあれば、そのまま加算、そうでなければ、1こ引く
there_is = True
flg = False
for i in index_tate:
    for j in index_yoko:
        #print(i+1, j+1)
        if((i+1, j+1) in bomb):
            dammy = True
        else:
            there_is = False
            flg = True
            break
    if flg:
        break

if(there_is):
    print(tate_max + yoko_max - 1)
else:
    print(tate_max + yoko_max)


        




'''
#tate_max = [i for i, v in enumerate(tate) if v == max(tate)]
np_list_tate = np.array(tate)
np_list_yoko = np.array(yoko)
tate_max = np_list_tate.argmax()
yoko_max = np_list_yoko.argmax()
print(tate_max, yoko_max)
'''

Submission status: Accepted

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

L = [ 0 for i in range(M)]
for i in range(M):
  L[i] = tuple( map(int, input().split()) )

H_val = [ 0 for i in range(H+1)]
W_val = [ 0 for i in range(W+1)]

H_key = {}
for i in L:
  if i[0] in H_key:
    H_key[ i[0] ].add( i[1] )
  else:
    H_key[ i[0] ] = {i[1]}

for i in L:
  H_val[ i[0] ] += 1
  W_val[ i[1] ] += 1
  
Hm = 0
Hs = set()
Wm = 0
Ws = set()
for i in range(1, H+1):
  if H_val[i] == Hm:
    Hs.add(i)
  elif H_val[i] > Hm:
    Hs = {i}
    Hm = H_val[i]
for i in range(1, W+1):
  if W_val[i] == Wm:
    Ws.add(i)
  elif W_val[i] > Wm:
    Ws = {i}
    Wm = W_val[i]
  
flg = False
for i in Hs:
  for j in Ws:
    if j not in H_key[i]:
      flg = True
      break
  if flg:
    break
if flg:
  print( Hm + Wm )
else:
  print( Hm + Wm - 1)

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase


def main():
    h, w, m = map(int, input().split())
    row = [0] * h
    col = [0] * w
    d = set()
    ma = 0
    for i in range(m):
        x, y = map(int, input().split())
        row[x - 1] += 1
        col[y - 1] += 1
        d.add((x, y))
    e=max(row)
    f=row.index(e)
    g=max(col)
    z=col.index(g)
    for i in range(w):
        ma=max(ma,e+col[i]-(1 if (f+1,i+1) in d else 0))
    for i in range(h):
        ma=max(ma,g+row[i]-(1 if (i+1,z+1) in d else 0))
    print(ma)
# region fastio
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

H, W, M = MAP()
hw = [LIST() for _ in range(M)]

cnt_h = [0]*(H+1)
cnt_w = [0]*(W+1)

for h, w in hw:
	cnt_h[h] += 1
	cnt_w[w] += 1

h_max = max(cnt_h)
y = [0]*(H+1)
c_y = 0
for i in range(H+1):
	if cnt_h[i] == h_max:
		y[i] += 1


w_max = max(cnt_w)
x = [0]*(W+1)
for i in range(W+1):
	if cnt_w[i] == w_max:
		x[i] += 1

c = 0
for h, w in hw:
	if y[h] == 1 and x[w] == 1:
		c += 1

if c == sum(x)*sum(y):
	print(w_max+h_max-1)
else:
	print(w_max+h_max)

Submission status: Accepted

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

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

for i in range(m):
    yoko[hw[i][0]] += 1
    tate[hw[i][1]] += 1
    
ans = 0

t_max = -1


for i in range(1,w+1):
    if t_max < tate[i]:
        t_max = tate[i]
        t_max_idx = []
        t_max_idx.append(i)
    elif t_max == tate[i]:
        t_max_idx.append(i)

y_max = -1

for i in range(1,h+1):
    if y_max < yoko[i]:
        y_max = yoko[i]
        y_max_idx = []
        y_max_idx.append(i)
    elif y_max == yoko[i]:
        y_max_idx.append(i)
        
s_y = set(y_max_idx)
s_t = set(t_max_idx)

if len(y_max_idx)*len(t_max_idx) > m:
    print(t_max+y_max)
else:
    ans = 0
    for i in range(m):
        if hw[i][0] in s_y and hw[i][1] in s_t:
            ans += 1
    if ans < len(y_max_idx)*len(t_max_idx):
        print(t_max+y_max)
    else:
        print(t_max+y_max-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

h, w, m = map(int, input().split())
List = [list(map(int, input().split())) for i in range(m)]
B = set()
for e in List:
    B.add(tuple(e))

hb = [0]*h
wb = [0]*w
for e in B:
    hb[e[0]-1] += 1
    wb[e[1]-1] += 1

hm = max(hb)
wm = max(wb)

hlist = []
for i, e in enumerate(hb):
    if e == hm:
        hlist.append(i)
wlist = []
for i, e in enumerate(wb):
    if e == wm:
        wlist.append(i)

for he in hlist:
    for we in wlist:
        if (he+1, we+1) not in B:
            print(hm+wm)
            exit()

print(hm+wm-1)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
from collections import defaultdict, deque
h, w, m = map(int,input().split())
row = defaultdict(int)
col = defaultdict(int)
grid = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    row[x]+=1
    col[y]+=1
    grid[(x,y)]=1


row = sorted(list(row.items()), key = lambda x: x[1], reverse = True)
col = sorted(list(col.items()), key = lambda x: x[1], reverse = True)


#print(row)
#print(col)

t = len(row)
for idx, ele in enumerate(row):
    i,j = ele
    if j!=row[0][1]:
        t = idx
        break
row = row[:t]
t = len(col)
for idx, ele in enumerate(col):
    i,j = ele
    if j!=col[0][1]:
        t = idx
        break
col = col[:t]

#print(row)
#print(col)
#print(grid)

ans = row[0][1]+col[0][1] + (-1 if grid[(row[0][0], col[0][0])] else 0)

i,j = 0,0
for r,cr in row:
    for c,cc in col:
        if not grid[(r,c)]:
            ans = cr+cc
            break
print(ans)


# dq = deque([(i,j)])
# while dq:
#     i,j = dq.popleft()
#     temp = row[i][1]+col[j][1] + (-1 if grid[(row[i][0], col[j][0])] else 0)
#     if ans<temp:
#         ans = temp
#         break
    
#     if i+1<len(row):dq.append((i+1,j))
#     if j+1<len(col):dq.append((i,j+1))

    
# print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W, M = map(int, input().split())

h_list = [0 for _ in range(H + 1)]
w_list = [0 for _ in range(W + 1)]
m_dic = {}
for i in range(M):
    h, w = map(int, input().split())
    h_list[h] += 1
    w_list[w] += 1
    m_dic["{}_{}".format(h, w)] = 1

max_h_list = []
max_h = -1
for i in range(H + 1):
    if max_h == h_list[i]:
        max_h_list.append(i)
    elif max_h < h_list[i]:
        max_h = h_list[i]
        max_h_list = [i]

max_w_list = []
max_w = -1
for i in range(W + 1):
    if max_w == w_list[i]:
        max_w_list.append(i)
    elif max_w < w_list[i]:
        max_w = w_list[i]
        max_w_list = [i]

adjust_dupl = 1
for i in range(len(max_h_list)):
    for j in range(len(max_w_list)):
        if "{}_{}".format(max_h_list[i], max_w_list[j]) not in m_dic:
            adjust_dupl = 0
            break
    if adjust_dupl == 0:
        break
print(max_h + max_w - adjust_dupl)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(H: int, W: int, M: int, h: "List[int]", w: "List[int]"):
    hDict = defaultdict(int)
    wDict = defaultdict(int)
    points = set()
    for i in range(M):
        hDict[h[i]]+=1
        wDict[w[i]]+=1
        points.add((h[i],w[i]))
    hArr = []
    wArr = []
    for hd in hDict:
        he = hDict[hd]
        hArr.append((-he,he,hd))
    for wd in wDict:
        he = wDict[wd]
        wArr.append((-he,he,wd))
    hArr.sort()
    wArr.sort()
    m = 0
    hm = hArr[0][1]
    wm = wArr[0][1]
    # hm+wm or hm+wm -1
    for h in hArr:
        if h[1] < hm:
            break
        for w in wArr:
            if w[1] < wm:
                break
            c = h[1] + w[1]
            if (h[2],w[2]) in points:
                c -= 1
            else:
                print(c)
                return
            m = max(m,c)
    print(m)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    h = [int()] * (M)  # type: "List[int]"
    w = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        h[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(H, W, M, h, w)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys

*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    return data.pop()

h, w, m = inp(), inp(), inp()


targets = set()
xs = []
ys = []
for _ in range(m):
    y, x = inp(), inp()
    # y -= 1
    # x -= 1
    ys.append(y)
    xs.append(x)
    targets.add((y, x))

x_stat = collections.Counter(xs)
y_stat = collections.Counter(ys)

xs = sorted(set(xs), key=lambda obj: x_stat[obj], reverse=True)
ys = sorted(set(ys), key=lambda obj: y_stat[obj], reverse=True)

mx_x = x_stat[xs[0]]
mx_y = y_stat[ys[0]]
while xs and x_stat[xs[-1]] < x_stat[xs[0]]:
    xs.pop()
while ys and y_stat[ys[-1]] < y_stat[ys[0]]:
    ys.pop()
# print(xs, x_stat)
# print(ys, y_stat)

found = False
for x in xs:
    for y in ys:
        if (y, x) not in targets:
            found = True
            break
    if found:
        break
ans = mx_y + mx_x
if not found:
    ans -= 1
print(ans)

Submission status: Accepted

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

yoko=[0 for i in range(w)]
tate=[0 for j in range(h)]

for i in range(m):
    yoko[hw[i][0]-1]+=1
    tate[hw[i][1]-1]+=1

mt =max(tate)
my=max(yoko)

cu=yoko.count(my)*tate.count(mt)
c=0
for i in range(m):
    if yoko[hw[i][0]-1]==my and tate[hw[i][1]-1]==mt:
        # print(hw[i])
        c+=1
ans= mt+my
# print(tate,yoko)
# print(c,cu)
if c== cu:
    ans-=1
print(ans)

Submission status: Accepted

Solution code:
import bisect
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    wlis = sorted(havew[hs[0]])
    for ws in dicwi:
        if ws[1] != wmax:
            break
        idx = bisect.bisect_left(wlis, ws[0])
        if idx >= len(wlis):
            print(hmax+wmax)
            exit()
        if ws[0] != wlis[idx]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

Submission status: Accepted

Solution code:
import collections
import sys

*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    return data.pop()

h, w, m = inp(), inp(), inp()


targets = set()
xs = []
ys = []
for _ in range(m):
    y, x = inp(), inp()
    # y -= 1
    # x -= 1
    ys.append(y)
    xs.append(x)
    targets.add((y, x))

x_stat = collections.Counter(xs)
y_stat = collections.Counter(ys)

xs = sorted(set(xs), key=lambda obj: x_stat[obj], reverse=True)
ys = sorted(set(ys), key=lambda obj: y_stat[obj], reverse=True)

mx_x = x_stat[xs[0]]
mx_y = y_stat[ys[0]]
while xs and x_stat[xs[-1]] < x_stat[xs[0]]:
    xs.pop()
while ys and y_stat[ys[-1]] < y_stat[ys[0]]:
    ys.pop()
# print(xs, x_stat)
# print(ys, y_stat)

found = False
for x in xs:
    for y in ys:
        if (y, x) not in targets:
            found = True
            break
ans = mx_y + mx_x
if not found:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

H, W, M = map(int, input().split())
h_count = [[i, 0] for i in range(H)]
w_count = [[i, 0] for i in range(W)]
exist = dict()
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    h_count[h][1] += 1
    w_count[w][1] += 1
    exist[(h, w)] = True

h_count.sort(key=itemgetter(1), reverse=True)
w_count.sort(key=itemgetter(1), reverse=True)
h_max = h_count[0][1]
w_max = w_count[0][1]
res = 0
is_dup = True
for h in h_count:
    if h[1] != h_max or not is_dup:
        break
    for w in w_count:
        if w[1] != w_max or not is_dup:
            break
        val = h[1] + w[1]
        if exist.get((h[0], w[0]), False):
            val -= 1
        else:
            is_dup = False
        res = max(res, val)
print(res)

Submission status: Accepted

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

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

    H_list = [[0, i] for i in range(H + 1)] 
    W_list = [[0, i] for i in range(W + 1)] 


    S = set()
    S_add = S.add
    INF = 10 ** 6

    for _ in range(M):
        a, b = map(int, input().split())
        tmp = INF * a + b
        S_add(tmp)
        H_list[a][0] += 1
        W_list[b][0] += 1

    ans = 0
    H_list.sort(reverse=True)
    W_list.sort(reverse=True)

    tmp_H = H_list[0][0]
    tmp_W = W_list[0][0]
    tmp_ans = tmp_H + tmp_W

    for h in range(H):
        if H_list[h][0] + 1 < tmp_H:
            continue
        h_ = H_list[h][1]
        H_ = H_list[h][0]
        for w in range(W):
            if W_list[w][0] + H_ + 1 < tmp_ans:
                break
            w_ = W_list[w][1]
            tmp = H_ + W_list[w][0]
            if INF * h_ + w_ in S:
                tmp -= 1
            ans = max(ans, tmp)
            if ans == tmp_ans:
                print (ans)
                return

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
x=[]
y=[]
from collections import deque
for i in range(m):
    h1,w1=map(int,input().split())
    x.append([h1,w1])
    y.append([w1,h1])
x.sort()
y.sort()
a=0
b=0
s=0
t=0
ans1=0
ans2=0
for i in range(m):
    if a==x[i][0]:
        s+=1
    else:
        a=x[i][0]        
        ans1=max(ans1,s)
        s=1
ans1=max(ans1,s)
for i in range(m):
    if b==y[i][0]:
        t+=1
    else:
        b=y[i][0]
        ans2=max(ans2,t)
        t=1
ans2=max(ans2,t)
a=0
b=0
s=0
t=0
d=deque()
e=deque()
for i in range(m):
    if a==x[i][0]:
        s+=1
    else:
        if s==ans1:
            d.append(a)
        a=x[i][0]
        s=1
if s==ans1:
    d.append(a)
for i in range(m):
    if b==y[i][0]:
        t+=1
    else:
        if t==ans2:
            e.append(b)
        b=y[i][0]
        t=1
if t==ans2:
    e.append(b)
ab=len(d)*len(e)
n=[]
for i in range(m):
    if x[i][0]==d[0]:
        n.append(x[i][1])
    elif x[i][0]>d[0]:
        d.popleft()
        if len(d)==0:
            break
        if x[i][0]==d[0]:
            n.append(x[i][1])
n.sort()
p=0
for i in range(len(n)):
    if n[i]==e[0]:
        p+=1
    elif n[i]>e[0]:
        e.popleft()
        if len(e)==0:
            break
        if n[i]==e[0]:
            p+=1
if p==ab:
    print(ans1+ans2-1)
else:
    print(ans1+ans2)

Submission status: Accepted

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

def main():
    H, W, M = map(int, input().split())
    bomb = set()
    yoko = [0] * W
    tate = [0] * H
    for _ in range(M):
        h, w = map(int, input().split())
        bomb.add((h-1, w-1))
        yoko[w - 1] += 1
        tate[h - 1] += 1

    idx_yoko = [(yoko[i], i) for i in range(W)]
    idx_tate = [(tate[i], i) for i in range(H)]
    idx_yoko.sort(reverse=True, key=lambda x: (x[0], x[1]))
    idx_tate.sort(reverse=True, key=lambda x: (x[0], x[1]))
    ans = 0

    yoko_bomb, idx_w = idx_yoko[0]
    tate_bomb_max = idx_tate[0][0]
    for tate_bomb, idx_h in idx_tate:
        if tate_bomb != tate_bomb_max: break
        if (idx_h, idx_w) not in bomb:
            print(yoko_bomb + tate_bomb)
            return

    tate_bomb, idx_h = idx_tate[0]
    yoko_bomb_max = idx_yoko[0][0]
    for yoko_bomb, idx_w in idx_yoko:
        if yoko_bomb != yoko_bomb_max: break
        if (idx_h, idx_w) not in bomb:
            print(yoko_bomb + tate_bomb)
            return

    print(yoko_bomb_max + tate_bomb_max - 1)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
countH=[0]*(H+1)
countW=[0]*(W+1)
S={}
i=0
for _ in range(M):
    h,w=map(int,input().split())
    countH[h]+=1
    countW[w]+=1
    S[str(h)+','+str(w)]=1

mh=max(countH)
mw=max(countW)
ans=mh+mw-1

c_mh=[]
i=0
while i<=H:
    if countH[i]==mh:
        c_mh.append(i)
    i+=1

c_mw=[]
i=0
while i<=W:
    if countW[i]==mw:
        c_mw.append(i)
    i+=1

ok=0
ok1=0
ok2=0
for h in c_mh:
    for w in c_mw:
        S.setdefault(str(h)+','+str(w))
        if S[str(h)+','+str(w)]==1:
            continue
        else:
            ans+=1
            ok=1
        if ok:
            break
    if ok:
        break

print(ans)

Submission status: Accepted

Solution code:
import collections as c

h,w,m = map(int,input().split())
x = []
y = []
z = set([])
for i in range(m):
    s,t = map(int,input().split())
    x.append(s)
    y.append(t)
    z.add(tuple([s,t]))
a = c.Counter(x)
b = c.Counter(y)
a = a.most_common()
b = b.most_common()
c = []
d = []
e = a[0][1]
f = b[0][1]

for sa in a:
    if sa[1] == e:
        c.append(sa[0])
    else:
        break
for sb in b:
    if sb[1] == f:
        d.append(sb[0])
    else:
        break

fl = 0
ans = e+f-1
for s in c:
    for t in d:
        if tuple([s,t]) not in z:
            fl = 1
            ans += 1
            break
    if fl == 1:
        break
    
print(ans)

Submission status: Accepted

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

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

h = {}
w = {}
m = {}
for i in range(M):
    hi, wi = map(int, readline().split())
    if hi not in h:
        h[hi] = 1
        m[hi] = set()
        m[hi].add(wi)
    else:
        h[hi] += 1
        m[hi].add(wi)
    if wi not in w:
        w[wi] = 1
    else:
        w[wi] += 1

max_h = max(h.values())
max_w = max(w.values())
max_h_list = [kv[0] for kv in h.items() if kv[1] == max_h]
max_w_list = [kv[0] for kv in w.items() if kv[1] == max_w]

for i in max_h_list:
    for j in max_w_list:
        if j not in m[i]:
            print(max_h + max_w)
            exit()
print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, M: int, h: "List[int]", w: "List[int]"):
    from collections import defaultdict
    h = [hh - 1 for hh in h]
    w = [ww - 1 for ww in w]
    row_values, col_values = [0] * H, [0] * W
    for hh, ww in zip(h, w):
        row_values[hh] += 1
        col_values[ww] += 1
    max_row_value = max(row_values)
    max_col_value = max(col_values)
    max_rows = set(filter(lambda i: row_values[i] == max_row_value, range(H)))
    max_cols = set(filter(lambda i: col_values[i] == max_col_value, range(W)))
    intersections = defaultdict(set) # intersections[col]
    for hh, ww in zip(h, w):
        if ww not in max_cols:
            continue
        if hh not in max_rows:
            continue
        intersections[ww].add(hh)
    m = min([len(intersections[col]) for col in max_cols])
    return max_row_value + max_col_value - (1 if m == len(max_rows) else 0)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    h = [int()] * (M)  # type: "List[int]"
    w = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        h[i] = int(next(tokens))
        w[i] = int(next(tokens))
    print(solve(H, W, M, h, w))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()