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:
# cook your dish here
h,w,m=map(int,input().split())
a=[0 for i in range(h+1)]
b=[0 for i in range(w+1)]

v={}
for i in range(m):
    x,y=map(int,input().split())
    # v.append([x,y])
    v[(x,y)]=1
    a[x]+=1
    b[y]+=1
    

maxx=max(a)
aa=[]
for i in range(1,len(a)):
    if a[i]==maxx:
        aa.append(i)

maxy=max(b)
bb=[]
for i in range(1,len(b)):
    if b[i]==maxy:
        bb.append(i)

ans=0
flag=0
for i in range(len(aa)):
    for j in range(len(bb)):
        if (aa[i],bb[j]) in v:
            ans=max(ans,a[aa[i]]+b[bb[j]]-1)
            
        else:
            ans=max(ans,a[aa[i]]+b[bb[j]])
            flag=1
            break
        
    if flag==1:
        break
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
 
H,W,M = map(int,input().split())
hw = defaultdict(int)
 
h = [0]*H
w = [0]*W
 
for _ in range(M):
    hh,ww = map(int,input().split())
    h[hh-1] += 1
    w[ww-1] += 1
    hw[(hh-1,ww-1)] = 1
 
def returnMaxs(a):
    m = max(a)
    ind = []
    for i in range(len(a)):
        if a[i] == m:
            ind.append(i)
    return ind
 
ind_h = returnMaxs(h)
ind_w = returnMaxs(w)
 
m = h[ind_h[0]]+w[ind_w[0]]
 
if len(ind_h)*len(ind_w) > M:
    print(m)
else:
    flag = False
    for i in ind_h:
        for j in ind_w:
            if hw[(i,j)] == 0:
                flag = True
    
    if flag:
        print(m)
    else:
        print(m-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w,m=map(int,input().split())
p=[0]*h
q=[0]*w
lis=set()
for i in range(m):
	a,b=map(int,input().split())
	p[a-1]+=1
	q[b-1]+=1
	lis.add(10**6*(a-1)+b-1)
P=max(p)
Q=max(q)
r=[]
l=[]
for i in range(h):
	if p[i]==P:
		r.append(i)
for i in range(w):
	if q[i]==Q:
		l.append(i)
if len(r)*len(l)>m:
	print(P+Q)
	exit()
f=0
for x in r:
	for y in l:
		if x*10**6+y in lis:
			continue
		else:
			f=1
			break
print(P+Q-1+f)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, M = mapint()
from collections import Counter, defaultdict
h_count = Counter()
w_count = Counter()
dic = [set() for _ in range(W)]
for _ in range(M):
    h, w = mapint()
    h_count[h] += 1
    w_count[w] += 1
    dic[w-1].add(h)

h_max = 0
h_set = set()
for i, (num, cnt) in enumerate(h_count.most_common()):
    if i==0:
        h_max = cnt
        h_set.add(num)
    else:
        if cnt<h_max:
            break
        else:
            h_set.add(num)
w_max = 0
for i, (num, cnt) in enumerate(w_count.most_common()):
    if i==0:
        w_max = cnt
    if cnt<w_max:
        print(w_max+h_max-1)
        exit()
    else:
        if h_set-dic[num-1]:
            print(cnt+h_max)
            exit()
print(w_max+h_max-1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
hw=[list(map(int,input().split())) for _ in range(m)]
numh=[[i,0] for i in range(h)]
numw=[[i,0] for i in range(w)]
d=set(())
for hi,wi in hw:
  numh[hi-1][1]+=1
  numw[wi-1][1]+=1
  d.add((hi-1,wi-1))
numh.sort(key=lambda x:x[1])
numw.sort(key=lambda x:x[1])
ansh=numh[-1][1]
answ=numw[-1][1]
if ansh+answ==1:
  print(1)
  exit()
# 答えはansh+answまたはansh+answ-1
hk=set(())
while numh and numh[-1][1]==ansh:
  hk.add(numh.pop()[0])
wk=set(())
while numw and numw[-1][1]==answ:
  wk.add(numw.pop()[0])

for wi in wk:
  for hi in hk:
    if (hi,wi) not in d:
      print(ansh+answ)
      exit()
print(ansh+answ-1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50



def run():
    H, W, M = map(int, sysread().split())
    Hs = defaultdict(lambda:0)
    Ws = defaultdict(lambda:0)
    hws = set()
    for i in range(M):
        h,w = map(int, sysread().split())
        hws.add((h,w))
        Hs[h] += 1
        Ws[w] += 1

    max_hs = []
    max_h_val = max(Hs.values())
    for h, count in Hs.items():
        if count == max_h_val:
            max_hs.append(h)

    max_ws = []
    max_w_val = max(Ws.values())
    for w, count in Ws.items():
        if count == max_w_val:
            max_ws.append(w)
    #print(Hs)
    #print(Ws)
    #print(hws)
    #print(max_w_val)
    #print(max_ws)
    for hh in max_hs:
        for ww in max_ws:
            if not (hh, ww) in hws:
                print(max_h_val + max_w_val)
                return
    print(max_h_val + max_w_val - 1)




if __name__ == "__main__":
    run()

Submission status: Accepted

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

freq_w = [ 0 for _ in range(W)]
freq_h = [ 0 for _ in range(H)]
pos = dict()

for _ in range(M):
    h, w = map(int, input().split())
    freq_h[h-1] += 1
    freq_w[w-1] += 1
    pos[(h-1, w-1)] = True


m_w = max(freq_w)
pos_w = [i for i, j in enumerate(freq_w) if j == m_w]

m_h = max(freq_h)
pos_h = [i for i, j in enumerate(freq_h) if j == m_h]

max_ = m_w + m_h - 1
found = False
#
# for el in pos:
#     i, j = el
#     max_

for i in pos_h:
    for j in pos_w:
        if not((i, j) in pos):
            found = True
            break
    if found == True:
        break

print(max_ + int(found))

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
X = [0 for i in range(H)]
Y = [0 for j in range(W)]
combi = []
for k in range(M):
    pos = list(map(int,input().split()))
    X[pos[0]-1]+=1
    Y[pos[1]-1]+=1
    combi.append(1000000007*pos[0]+pos[1])
a = max(X)
b = max(Y)
X_max = [0 for d in range(H)]
Y_max = [0 for e in range(W)]
for l in range(H):
    if X[l] == a:
        X_max[l]+=1
for m in range(W):
    if Y[m] == b:
        Y_max[m]+=1
X_count = X_max.count(1)
Y_count = Y_max.count(1)
chance = X_count*Y_count
flg = 1
for s in combi:
    ans1 = s//1000000007
    ans2 = s % 1000000007
    if X_max[ans1-1]==1 and Y_max[ans2-1]==1:
        chance-=1
if chance > 0:
    flg = 0
print(a + b - flg)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
HH=[0 for i in range(h+1)]
WW=[0 for i in range(w+1)]
Q=[]
for i in range(m):
    a,b=map(int,input().split())
    HH[a]+=1
    WW[b]+=1
    Q.append((a,b))

Q.sort()
head=0

maxH=max(HH)
maxW=max(WW)

HHH=[]
for i in range(h+1):
    if HH[i]==maxH:
        HHH.append(i)

WWW=[]
for i in range(w+1):
    if WW[i]==maxW:
        WWW.append(i)

ans=maxH+maxW
flg=-1
end=False
for i in HHH:
    for q in WWW:
        while (i,q)!=Q[head]:
            head+=1
            if head==m:
                flg=0
                end=True
                break     
        if end:
            break
    if end:
        break
print(ans+flg)

Submission status: Accepted

Solution code:
from collections import Counter

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

    retu = Counter()
    gyo = Counter()

    ipt = [set() for _ in range(H)]

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].add(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
p = []
hlist = [0 for i in range(h)]
wlist = [0 for i in range(w)]
for i in range(m):
    a,b = map(int,input().split())
    hlist[a-1] += 1
    wlist[b-1] += 1
    p.append([a-1,b-1])
q = 0
for i in range(h):
    q = max(q,hlist[i])
s = []
for i in range(h):
    if hlist[i] == q:
        s.append(i)
r = 0
for i in range(w):
    r = max(r,wlist[i])
t = []
for i in range(w):
    if wlist[i] == r:
        t.append(i)
z = 0
for i in range(m):
    if hlist[p[i][0]] == q and wlist[p[i][1]] == r:
        z += 1
if z == len(s)*len(t):
    print(q+r-1)
else:
    print(q+r)

Submission status: Accepted

Solution code:
def main():
    H, W, M = map(int, input().split())
    targets = set()
    totalH = [0] * H
    totalW = [0] * W
    for _ in range(M):
        h, w = map(lambda x: int(x)-1, input().split())
        totalH[h] += 1
        totalW[w] += 1
        targets.add((h, w))
    maxH = max(totalH)
    maxW = max(totalW)
    maxHindex = set()
    maxWindex = set()
    for i in range(H):
        if totalH[i] == maxH:
            maxHindex.add(i)
    for i in range(W):
        if totalW[i] == maxW:
            maxWindex.add(i)
    relatedTargets = set()
    for h, w in targets:
        if h in maxHindex and w in maxWindex:
            relatedTargets.add((h, w))
    if len(relatedTargets) == len(maxHindex) * len(maxWindex):
        print(maxH + maxW - 1)
    else:
        print(maxH + maxW)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
Nh = [0]*(H+1)
Nw = [0]*(W+1)
HW = []
for _ in range(M):
    h, w = map(int, input().split())
    HW.append((h,w))

    Nh[h] += 1
    Nw[w] += 1

maxH = max(Nh)
Ih = [False] * (H+1)
xh = 0
for ih, nh in enumerate(Nh):
    if nh==maxH:
        Ih[ih] = True
        xh += 1

maxW = max(Nw)
Iw = [False] * (W+1)
xw = 0
for iw, nw in enumerate(Nw):
    if nw==maxW:
        Iw[iw] = True
        xw += 1

n = 0
for ih, iw in HW:
    if Ih[ih] and Iw[iw]: n+=1

ans = maxH+maxW
print(ans if n<xh*xw else ans-1)

Submission status: Accepted

Solution code:
H, W, M = map(int,input().split())
H_dict = dict()
W_dict = dict()
mines = set()

for i in range(M):
    h,w = map(int,input().split())
    mines.add((h,w))
    if h in H_dict.keys():
        H_dict[h] += 1
    else:
        H_dict[h] = 1
    
    if w in W_dict.keys():
        W_dict[w] += 1
    else:
        W_dict[w] = 1
tmp = 0 
H_max = list()
W_max = list()

for key in H_dict.keys():
    if H_dict[key] > tmp:
        tmp = H_dict[key]
        H_max = list()
        H_max.append(key)
    elif H_dict[key] == tmp:
        H_max.append(key)
ans_h = tmp
tmp = 0        

for key in W_dict.keys():
    if W_dict[key] > tmp:
        tmp = W_dict[key]
        W_max = list()
        W_max.append(key)
    elif W_dict[key] == tmp:
        W_max.append(key)
ans_w = tmp
        
flag = False
for h in H_max:
    for w in W_max:
        if (h,w) not in mines:
            flag = True
            break

if flag:
    print(ans_w + ans_h)
else:
    print(ans_w + ans_h -1)


#print(H_max)
#print(ans_h)
#print(W_max)
#print(ans_w)
#print(mines)

Submission status: Accepted

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

DX={}
DY={}
D={}
for i in range(M):
    a,b=map(int,input().split())
    D[(a,b)]=1
    if a not in DX:
        DX[a]=1
    else:
        DX[a]+=1
    if b not in DY:
        DY[b]=1
    else:
        DY[b]+=1

MAXX=0
MXL=[]
for k,v in DX.items():
    if MAXX==v:
        MXL.append(k)
    elif MAXX<v:
        MAXX=v
        MXL=[k]
MAXY=0
MYL=[]
for k,v in DY.items():
    if MAXY==v:
        MYL.append(k)
    elif MAXY<v:
        MAXY=v
        MYL=[k]

ans=MAXX+MAXY-1
for x in MXL:
    for y in MYL:
        if (x,y) not in D:
            print(MAXX+MAXY)
            exit()
print(ans)

Submission status: Accepted

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

class SegmentTree():
    def __init__(self, n, init):
        self.n = 2 ** (n - 1).bit_length()
        self.init = init
        self.data = [init] * (2 * self.n)

    def inc(self, k):
        self.data[k + self.n - 1] += 1

    def build(self):
        for k in reversed(range(self.n - 1)):
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def update(self, k, a):
        k += self.n - 1
        self.data[k] += a

        while k > 0:
            k = (k - 1) // 2
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def query(self, l, r):
        L = l + self.n
        R = r + self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret



if __name__ == "__main__":
    H, W, M = map(int, input().split())

    Seg = SegmentTree(W + 5, 0)

    Yaxis = dict()

    for _ in range(M):
        h, w = map(int, input().split())
        if h in Yaxis: Yaxis[h].append(w)
        else: Yaxis[h] = [w]
        Seg.inc(w)

    Seg.build()


    ans = 0
    for y in Yaxis:
        for x in Yaxis[y]: Seg.update(x, -1)
        ans = max(ans, len(Yaxis[y]) + Seg.query(0, W + 1))
        for x in Yaxis[y]: Seg.update(x, 1)

    print(ans)

Submission status: Accepted

Solution code:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################

HH,WW,MM = map(int, input().split())

H=[0] * HH
W=[0] * WW

from collections import defaultdict
d = defaultdict(int)

for _ in range(MM):
  nh,nw = map(int, input().split())
  h = nh - 1
  w = nw - 1
  d[h * 1000000 + w] = 1
  H[h] += 1
  W[w] += 1

hm = max(H)
wm = max(W)

# _p(hm,wm)
# _pa(M)

HI = [i for i, x in enumerate(H) if x == hm]
WI = [i for i, x in enumerate(W) if x == wm]

# _p(HI)
# _p(WI)

ans = hm + wm
for h in HI:
  for w in WI:
    if d[h * 1000000 + w] == 0:
      print(ans)
      exit()

print(ans-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

h = [0]*H
w = [0]*W

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

def returnMaxs(a):
    m = max(a)
    ind = []
    for i in range(len(a)):
        if a[i] == m:
            ind.append(i)
    return ind

ind_h = returnMaxs(h)
ind_w = returnMaxs(w)

m = h[ind_h[0]]+w[ind_w[0]]

if len(ind_h)*len(ind_w) > M:
    print(m)
else:
    flag = False
    for i in ind_h:
        for j in ind_w:
            if hw[(i,j)] == 0:
                flag = True
    
    if flag:
        print(m)
    else:
        print(m-1)

Submission status: Accepted

Solution code:
h, w, m = [int(e) for e in input().split()]

htotal = [0] * h
wtotal = [0] * w


hmax = 0
wmax = 0

s = set()
hl = []
wl = []

for i in range(m):
    hi, wi = [int(e) for e in input().split()]
    hi -= 1
    wi -= 1

    s.add((hi, wi))
    htotal[hi] += 1
    wtotal[wi] += 1

    if htotal[hi] > hmax:
        hmax = htotal[hi]
        hl = [hi]
    elif htotal[hi] == hmax:
        hl.append(hi)

    if wtotal[wi] > wmax:
        wmax = wtotal[wi]
        wl = [wi]
    elif wtotal[wi] == wmax:
        wl.append(wi)

m = hmax + wmax - 1
for he in hl:
    if m == hmax + wmax:
        break
    for we in wl:
        if m == hmax + wmax:
            break
        if not (he, we) in s:
            m += 1

print(m)

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:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W, M = map(int, input().split())
h = [] * M
w = [] * M
dic_combi = defaultdict(int)

for _ in range(M):
    h_, w_ = map(int, input().split())
    h.append(h_)
    w.append(w_)
    dic_combi[h_ * (10**6) +  w_]=1

dic_h = Counter(h)
dic_w = Counter(w)
# print(dic_h, dic_w)
max_h_key = max(dic_h.items(), key=lambda x:x[1])[0]
max_w_key = max(dic_w.items(), key=lambda x:x[1])[0]

max_h = dic_h[max_h_key]
max_w = dic_w[max_w_key]

keys_h = [k for k, v in dic_h.items() if v == max_h]
keys_w = [k for k, v in dic_w.items() if v == max_w]


ans = 0
for ind_h in keys_h:
    for ind_w in keys_w:
        ret = max_h + max_w
        if dic_combi[ind_h*(10**6) + ind_w] == 1:
            ret -= 1
        else:
            print(ret)
            sys.exit()
        ans = max(ans, ret)

print(ans)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
a = [0]*h; b = [0]*w; c = {}
for _ in range(m):
    H, W = map(int, input().split())
    H -= 1; W -= 1
    a[H] += 1; b[W] += 1
    c[H*10**6+W] = 0
amaxvalue = max(a); bmaxvalue = max(b)
amaxkey = []; bmaxkey = []
for i in range(h):
    if a[i] == amaxvalue: amaxkey.append(i)
for i in range(w):
    if b[i] == bmaxvalue: bmaxkey.append(i)
d = 0
for i in range(len(amaxkey)):
    for j in range(len(bmaxkey)):
        if amaxkey[i]*10**6+bmaxkey[j] not in c:
            print(amaxvalue+bmaxvalue)
            d = 1
            break
    if d == 1: break
else: print(amaxvalue+bmaxvalue-1)

Submission status: Accepted

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

hl = [0]*(h+1)
wl = [0]*(w+1)

hw_set = set()
for _ in range(m):
    ch,cw = map(int, input().split())
    hl[ch] += 1
    wl[cw] += 1
    hw_set.add((ch,cw))

hl_vi = []
for i, v in enumerate(hl):
    hl_vi.append((v,i))
hl_vi.sort(reverse=True)

wl_vi = []
for i, v in enumerate(wl):
    wl_vi.append((v,i))
wl_vi.sort(reverse=True)

max_h = hl_vi[0][0]
max_hil = []
for v,i in hl_vi:
    if v == max_h:
        max_hil.append(i)

max_w = wl_vi[0][0]
max_wil = []
for v,i in wl_vi:
    if v == max_w:
        max_wil.append(i)


for hi in max_hil:
    for wi in max_wil:
        if not (hi,wi) in hw_set:
            ans = max_h + max_w
            print(ans)
            exit()
            
ans = max_h + max_w
print(ans-1)

# print(max_hil)
# print(max_wil)

# print(hl_vi)
# print(wl_vi)
# ans = hl_vi[0][0] + wl_vi[0][0]
# if (hl_vi[0][1], wl_vi[0][1]) in hw_set:
#     ans-=1

# print(ans)

Submission status: Accepted

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

bombs = set()
for _ in range(M):
	y, x = map(int, input().split())
	bombs.add((x - 1, y - 1))

counts_v = [0] * W
counts_h = [0] * H
for x, y in bombs:
	counts_v[x] += 1
	counts_h[y] += 1

max_h = max(counts_h)
max_v = max(counts_v)

max_x_list = []
max_y_list = []

for x in range(W):
	if max_v == counts_v[x]:
		max_x_list.append(x)

for y in range(H):
	if max_h == counts_h[y]:
		max_y_list.append(y)

def check():
	for x in max_x_list:
		for y in max_y_list:
			if (x, y) not in bombs:
				return True
	return False

total = max_h + max_v
if not check():
	total -= 1

print(total)

Submission status: Accepted

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

rowcts = [0] * H
colcts = [0] * W

bombs = set()
for _ in range(M):
    y, x = map(int, input().split())
    rowcts[y-1] += 1
    colcts[x-1] += 1
    bombs.add((y-1,x-1))

maxY = max(rowcts)
maxYidxs = []
for y in range(H):
    if rowcts[y] == maxY:
        maxYidxs.append(y)

maxX = max(colcts)
maxXidxs = []
for x in range(W):
    if colcts[x] == maxX:
        maxXidxs.append(x)

# たかだか 3*10^5 のはず
for y in maxYidxs:
    for x in maxXidxs:
        if (y, x) not in bombs:
            print(maxY + maxX)
            exit()
print(maxY + maxX - 1)

Submission status: Accepted

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

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

hl = [0] * H
wl = [0] * W
mem = set()

for h, w in hw :
  hl[h - 1] += 1
  wl[w - 1] += 1
  mem.add((h - 1, w - 1))
  
mh = max(hl)
mw = max(wl)

if mh == 0 :
  print(mw)
elif mw == 0 :
  print(mh)
else :
  hs = []
  ws = []
  for i, y in enumerate(hl) :
    if y == mh :
      hs.append((i, y))
  for i, x in enumerate(wl) :
    if x == mw :
      ws.append((i, x))


  ret = 0
  for x, w in ws :
    flag = False
    for y, h in hs :
      if (y, x) in mem :
        ret = max(ret, w + h - 1)
      else :
        ret = max(ret, w + h)
        flag = True
        break
    if flag :
      break
      
  print(ret)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

h,w,m=MI()
bomb=set()
row=[0]*h
col=[0]*w
for _ in range(m):
    i,j=MI1()
    row[i]+=1
    col[j]+=1
    bomb.add((i,j))
rmx=max(row)
cmx=max(col)
ii=[]
for i in range(h):
    if row[i]==rmx:ii.append(i)
jj=[]
for j in range(w):
    if col[j]==cmx:jj.append(j)
ans=rmx+cmx
for i in ii:
    for j in jj:
        if (i,j) not in bomb:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
H = [0]*(h+1)
W = [0]*(w+1)
d = {}
for i in range(m):
    x,y = map(int,input().split())
    d[(x,y)] = 1
    H[x] += 1
    W[y] += 1

mh = max(H)
mw = max(W)
la = []
lb = []
for i in range(h+1):
    if H[i] == mh:
        la.append(i)
    
for i in range(w+1):
    if W[i] == mw:
        lb.append(i)

ans = mh+mw-1

for i in la:
    for j in lb:
        if (i,j) not in d:
            print(ans+1)
            exit()
print(ans)

Submission status: Accepted

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

hh,ww,m = map(int,input().split())

dg = 10**6
HW = []

W = [0]*ww
for i in range(m):
    h,w = map(int,input().split())
    HW.append((h-1)*dg+w-1)
    W[w-1] += 1

ma = max(W)
c = 0
for e in W:
    if ma == e:
        c += 1

HW.sort()

res = 0

for i in range(hh):
    kf = bisect.bisect_left(HW,i*dg)
    ke = bisect.bisect_left(HW,(i+1)*dg)

    tmp = ke-kf
    ctr = 0
    for j in range(kf,ke):
        w = HW[j]%dg
        if W[w] == ma:
            ctr += 1
    if ctr == c:
        tmp += ma-1
    else:
        tmp += ma
    res = max(res,tmp)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W,M = map(int,input().split())
YX = [tuple(map(int,input().split())) for i in range(M)]
yxs = set(YX)

from collections import Counter
xc = Counter()
yc = Counter()
for y,x in YX:
    yc[y] += 1
    xc[x] += 1

ans = 0
for y,x in YX:
    ans = max(ans, yc[y] + xc[x] - 1)

xmc = xc.most_common()
ymc = yc.most_common()
xmx = xmc[0][1]
ymx = ymc[0][1]
for xk,xv in xmc:
    if xv < xmx: break
    for yk,yv in ymc:
        if yv < ymx: break
        if (yk,xk) in yxs: continue
        ans = max(ans, yv + xv)
        break
print(ans)

Submission status: Accepted

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

Ms = set([])

lstH = [0]*(H+1)
lstW = [0]*(W+1)

for _ in range(M):
  h, w =  map(int, input().split())
  lstH[h] += 1
  lstW[w] += 1
  Ms.add((h,w))

sH = set([])
sW = set([])
mH = max(lstH)
mW = max(lstW)

for i in range(1,H+1):
  if lstH[i] == mH:
    sH.add(i)
for i in range(1,W+1):
  if lstW[i] == mW:
    sW.add(i)
    
if len(sH)*len(sW) > 3* 10**5:
  print(mH+mW)
else:
  lst = set([])
  for h in sH:
    for w in sW:
      lst.add((h,w))
  for l in lst:
    if l not in Ms:
      print(mH+mW)
      exit()
  print(mH+mW-1)

Submission status: Accepted

Solution code:

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

s=set()
d={}
e={}
for i in range(m):
    a,b=list(map(int,input().split()))
    s.add((a,b))
    if a in d:
        d[a]+=1
    else:
        d[a]=1
    if b in e:
        e[b]+=1
    else:
        e[b]=1
ma=0
for i in e:
    ma=max(ma,e[i])
mi=0
for i in d:
    mi=max(mi,d[i])
a=[]
for i in d:
    if d[i]==mi:
        a.append(i)
b=[]
for i in e:
    if e[i]==ma:
        b.append(i)
r=0
for i in a:
    for j in b:
        if (i,j) not in s:
            r=1
            
            break
if r==1:
    print(mi+ma)
else:    
    print(ma+mi-1)

Submission status: Accepted

Solution code:
import sys

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

H_bomb = [0]*H
W_bomb = [0]*W
S = set()

for _ in range(m):
    h, w = map(int, sys.stdin.readline().split())
    h, w = h-1, w-1
    S.add(tuple([h, w]))
    H_bomb[h] += 1
    W_bomb[w] += 1

H_max = max(H_bomb)
W_max = max(W_bomb)

H_memo = []
W_memo = []

for i in range(H):
    if H_bomb[i] == H_max:
        H_memo.append(i)

for j in range(W):
    if W_bomb[j] == W_max:
        W_memo.append(j)

ans = H_max + W_max

for i in H_memo:
    for j in W_memo:
        if tuple([i, j]) not in S:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
import collections

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

my_s = set()

h_ls = []
w_ls = []

for _ in range(m):
    h_e, w_e = map(int, input().split())
    my_s.add((h_e, w_e))
    h_ls.append(h_e)
    w_ls.append(w_e)

h_c = collections.Counter(h_ls)
w_c = collections.Counter(w_ls)

h_ls = h_c.most_common()
w_ls = w_c.most_common()

h_ptr = 0
w_ptr = 0
ret = 0

h_idx, h_cnt = h_ls[0]
w_idx, w_cnt = w_ls[0]
tmp = h_cnt + w_cnt
flag = False
if (h_idx, w_idx) not in my_s:
    ret = tmp
else:
    for i, item in enumerate(h_ls):
        _, h_cnt_tmp = item
        if h_cnt_tmp != h_cnt:
            h_ptr = i - 1
            break
        if i == len(h_ls) - 1:
            h_ptr = len(h_ls) - 1

    for i, item in enumerate(w_ls):
        _, w_cnt_tmp = item
        if w_cnt_tmp != w_cnt:
            w_ptr = i - 1
            break
        if i == len(w_ls) - 1:
            w_ptr = len(w_ls) - 1

    for i in range(h_ptr+1):
        for j in range(w_ptr+1):
            h_idx, _ = h_ls[i]
            w_idx, _ = w_ls[j]
            if (h_idx, w_idx) not in my_s:
                ret = tmp
                flag = True
                break
        if flag:
            break
    if not flag:
        ret = tmp - 1

print(ret)

Submission status: Accepted

Solution code:
import itertools
H, W, M, *HW = [int(_) for _ in open(0).read().split()]
H += 1
W += 1
cnth = [0] * H
cntw = [0] * W
se = set((h, w) for h, w in zip(HW[::2], HW[1::2]))
for h in HW[::2]:
    cnth[h] += 1
maxcnth = max(cnth)
for w in HW[1::2]:
    cntw[w] += 1
maxcntw = max(cntw)
candidxh = [idxh for idxh, c in enumerate(cnth) if c == maxcnth]
candidxw = [idxw for idxw, c in enumerate(cntw) if c == maxcntw]
ans = maxcnth + maxcntw
for idxh, idxw in itertools.product(candidxh, candidxw):
    if (idxh, idxw) not in se:
        print(ans)
        exit()
print(ans - 1)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

Xs = [0] * (W + 1)
Ys = [0] * (H + 1)
s = set()

for p in P:
    Xs[p[1]] += 1
    Ys[p[0]] += 1
    s.add((p[1], p[0]))

xmax = max(Xs)
ymax = max(Ys)

XMs = []
YMs = []
for i in range(W + 1):
    if Xs[i] == xmax:
        XMs.append(i)

for i in range(H + 1):
    if Ys[i] == ymax:
        YMs.append(i)


def ans():
    for x in XMs:
        for y in YMs:
            if (x, y) not in s:
                return xmax + ymax

    return xmax + ymax - 1


if len(XMs) * len(YMs) > M:
    print(xmax + ymax)
else:
    print(ans())

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
hl=[0]*h
wl=[0]*w
s=set()
for i in range(m):
  hi,wi=map(int,input().split())
  hl[hi-1]+=1
  wl[wi-1]+=1
  s.add((hi-1)*w+wi-1)
mah=0
mahl=[]
for i in range(h):
  num=hl[i]
  if mah<num:
    mah=num
    mahl=[i]
  elif mah==num:
    mahl.append(i)
maw=0
mawl=[]
for i in range(w):
  num=wl[i]
  if maw<num:
    maw=num
    mawl=[i]
  elif num==maw:
    mawl.append(i)

frag=0
for hi in mahl:
  for wi in mawl:
    if not hi*w+wi in s:
      frag=1
      break
  if frag:break
if frag:
  print(mah+maw)
else:
  print(mah+maw-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    H,W,M = list(map(int,input().split()))
    from collections import defaultdict
    hdict = [0]*H
    wdict = [0]*W

    hw = []

    for i in range(M):
        h,w = list(map(int,input().split()))
        hdict[h-1]+=1
        wdict[w-1]+=1
        hw.append((h-1,w-1))

    hdict = [(i,c) for i,c in enumerate(hdict)]
    hdict.sort(key=lambda x:x[1],reverse=True)
    wdict = [(i,c) for i,c in enumerate(wdict)]
    wdict.sort(key=lambda x:x[1],reverse=True)

    hset = set([])
    hd = defaultdict(int)

    for i in range(H):
        if hdict[i][1]!=hdict[0][1]:
            break
        hset.add(hdict[i][0])
        hd[hdict[i][0]] = i

    wset = set([])
    wd = defaultdict(int)
    for i in range(W):
        if wdict[i][1]!=wdict[0][1]:
            break
        wset.add(wdict[i][0])
        wd[wdict[i][0]] = i

    if len(hset)*len(wset)>M:
        print(hdict[0][1]+wdict[0][1])
    else:
        DP = [[0]*len(wset) for i in range(len(hset))]
        for i in range(M):
            h,w = hw[i]
            if h in hset and w in wset:
                DP[hd[h]][wd[w]]=1
        
        if min(min(DP))==0:
            print(hdict[0][1]+wdict[0][1])
        else:
            print(hdict[0][1]+wdict[0][1]-1)

if __name__ == '__main__':
    main()