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:
#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

H,W,M = IL()

dicy = DD(int)
dicx = DD(int)
ame = []

for _ in range(M):
  y,x = IL()
  dicy[y-1] += 1
  dicx[x-1] += 1
  ame.append((y-1,x-1))

listy = DD(int)
listx = DD(int)
listy[0] = H-len(dicy)
listx[0] = W-len(dicx)

for k,v in dicy.items():
  listy[v] += 1
for k,v in dicx.items():
  listx[v] += 1

ymax = max(listy)
xmax = max(listx)
kouten = listy[ymax]*listx[xmax]

for y,x in ame:
  if dicy[y] == ymax and dicx[x] == xmax:
    kouten -= 1

if kouten == 0:
  print(ymax+xmax-1)
else:
  print(ymax+xmax)

Submission status: Accepted

Solution code:
import numpy as np
H,W,M=map(int, input().split())
hl=np.array([0 for i in range(H+1)])
wl=np.array([0 for i in range(W+1)])
ms=set()
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.add((h,w))
a=max(hl)
b=max(wl)
hmax=[]
wmax=[]
for i in range(len(hl)):
    if hl[i]==a:
        hmax.append(i)
for i in range(len(wl)):
    if wl[i]==b:
        wmax.append(i)
a=max(hl)
b=max(wl)
bl=False
if len(hmax)*len(wmax)>M:
    bl=True
else:
    for x in hmax:
        for y in wmax:
            if (x,y) not in ms:
                bl=True
                break
        if bl:
            break
if bl:
    print(a+b)
else:
    print(a+b-1)

Submission status: Accepted

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
from math import ceil

from heapq import heappop, heappush

def dijkstra(graph, alpha):
    n = len(graph)
    distance = [float("inf")]*n
    distance[alpha] = 0
    queue = [(0, alpha)]
    while queue:
        length, v = heappop(queue)
        for x, dist in graph[v]:
            if dist + length < distance[x]:
                distance[x] = dist + length
                heappush(queue, (dist+length, x))
    return distance

for _ in range(int(input()) if not True else 1):
    h, w, m = map(int, input().split())
    hw = []
    x = {}
    y = {}
    for i in range(m):
        xs, ys = list(map(int, input().split()))
        hw += [[xs, ys]]
        x[xs] = 1 if xs not in x else x[xs]+1
        y[ys] = 1 if ys not in y else y[ys]+1

    mx = max(x[k] for k in x)
    my = max(y[k] for k in y)

    ans = 0

    xx = set([k for k in x if x[k] == mx])
    yy = set([k for k in y if y[k] == my])
    c=0
    for xs, ys in hw:
        if xs in xx and ys in yy:
            c +=1
    print(mx+my - (c==len(xx)*len(yy)))

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b,c=[0]*h,[0]*w
for t1,t2 in a:
    b[t1-1]+=1
    c[t2-1]+=1
bm,cm=max(b),max(c)
b1,c1=[],[]
d=[]
for x,y in a:
    d.append((x-1,y-1))
d=set(d)
for i in range(h):
    if b[i]==bm:
        b1.append(i)
for i in range(w):
    if c[i]==cm:
        c1.append(i)
for i in b1:
    for j in c1:
        if (i,j) not in d:
            print(bm+cm)
            exit()
print(bm+cm-1)

Submission status: Accepted

Solution code:
# from sys import stdin
# input = stdin.readline
(H,W,M) = map(int, input().split())
hsum = [0]*H
wsum = [0]*W
bombs = set()
for _ in range(M):
    h,w = map(int, input().split())
    hsum[h-1] += 1
    wsum[w-1] += 1
    bombs.add((h-1,w-1))

hmax = max(hsum)
wmax = max(wsum)

cross_w_zero = False
hargmax = sum(1 for x in hsum if x == hmax)
wargmax = sum(1 for x in wsum if x == wmax)
cnt = sum(1 for h,w in bombs if hsum[h] == hmax and wsum[w] == wmax)
if hargmax * wargmax == cnt:
    print(hmax + wmax - 1)
else:
    print(hmax + wmax)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline

def main():
    H, W, M = map(int, readline().rstrip().split())
    HB = [0] * H
    WB = [0] * W
    HW = defaultdict(lambda : False)
    for _ in range(M):
        h, w = map(int, readline().rstrip().split())
        h -= 1
        w -= 1
        HW[(h,w)] = True
        HB[h] += 1
        WB[w] += 1
    hb = max(HB)
    max_h = [i for i, x in enumerate(HB) if x == hb]
    wb = max(WB)
    max_w = [i for i, x in enumerate(WB) if x == wb]
    
    ans = hb + wb
    for mh in max_h:
        for mw in max_w:
            if HW[(mh, mw)] == False:
                print(ans)
                sys.exit(0)
    print(ans - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
target = []
Height = [0] * H
Width = [0] * W
for m in range(M):
  h, w = map(lambda x: int(x)-1, input().split())
  target.append((h, w))
  Height[h] += 1
  Width[w] += 1
max_H, max_W = max(Height), max(Width)

cH, cW = 0, 0
for i in range(H):
  if Height[i] == max_H:
    cH +=1
for i in range(W):
  if Width[i] == max_W:
    cW +=1
max_cross = cH * cW

double_count = 0
for h, w in target:
  if Height[h] == max_H and Width[w] == max_W:
    double_count += 1

if double_count == max_cross:
  print(max_H + max_W - 1)
else:
  print(max_H + max_W)

Submission status: Accepted

Solution code:
h,w,m=map(int, input().split())
a=[0]*m
hc=[0]*w
wc=[0]*h
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[0]*w
wk=[0]*h
for i in range(len(hc)):
	if hc[i]==hcm:
		hk[i]=1
for i in range(len(wc)):
	if wc[i]==wcm:
		wk[i]=1
c=0
for i in range(len(a)):
	if wk[a[i][0]]==1 and hk[a[i][1]]==1:
		c+=1
if c==sum(hk)*sum(wk):
	print(hcm+wcm-1)		
else:
	print(hcm+wcm)

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
r = defaultdict(int)
c = defaultdict(int)
rc = defaultdict(int)
for i in range(M):
    h, w = map(int, input().split())
    rc[(h, w)] += 1
    r[w] += 1
    c[h] += 1

ri, rmax = 0, 0
ci, cmax = 0, 0
for i in r.keys():
    v = r[i]
    if v > rmax:
        ri = i
        rmax = v
for i in c.keys():
    v = c[i]
    if v > cmax:
        ci = i
        cmax = v

rml, cml = [], []
for i, v in r.items():
    if v == rmax:
        rml.append((i, v))
for i, v in c.items():
    if v == cmax:
        cml.append((i, v))


ans = rmax+cmax-1
for i, vi in rml:
    find = False
    for j, vj in cml:
        if not (j, i) in rc:
            ans += 1
            find = True
            break
    if find:
        break
print(ans)

Submission status: Accepted

Solution code:

H,W,M=map(int, input().split())
hl=[0 for i in range(H+1)]
wl=[0 for i in range(W+1)]
ms=[]
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.append([h,w])
a=max(hl)
b=max(wl)
hmax=[]
wmax=[]
s=0
for x in ms:
    if  hl[x[0]]==a and wl[x[1]]==b:
        s+=1
c=hl.count(a)
d=wl.count(b)
if s<c*d:
    print(a+b)
else:
    print(a+b-1)

Submission status: Accepted

Solution code:
from collections import*
(h,w,m),*z=[tuple(map(int,o.split()))for o in open(0)]
s=set(z)
y,x=[Counter(t).most_common()for t in zip(*z)]
a,b=y[0][1],x[0][1]
p=[i for i,v in y if v==a]
q=[i for i,v in x if v==b]
for i in p:
  for j in q:
    if(i,j)not in s:exit(print(a+b))
print(a+b-1)

Submission status: Accepted

Solution code:
(h,w,m),*s=[[*map(int,i.split())]for i in open(0)]
r,c=[0]*-~h,[0]*-~w
for x,y in s:
    r[x]+=1
    c[y]+=1
R,C=max(r),max(c)
print(R+C-(r.count(R)*c.count(C)==sum(r[x]+c[y]==R+C for x,y in s)))

Submission status: Accepted

Solution code:
from collections import defaultdict

def get_keys_of_max_value(d):
    v_max = 0
    keys = []
    for k, v in d.items():
        if v_max < v:
            v_max = v
            keys = [k]
        elif v_max == v:
            keys.append(k)
    return keys, v_max

h, w, m = map(int, input().split())
targets = {tuple(map(int, input().split())) for _ in range(m)}
n_r = defaultdict(int)
n_c = defaultdict(int)
for x, y in targets:
    n_r[x] += 1
    n_c[y] += 1

rows, n_r_max = get_keys_of_max_value(n_r)
columns, n_c_max = get_keys_of_max_value(n_c)

for r in rows:
    for c in columns:
        if (r, c) not in targets:
            print(n_r_max + n_c_max)
            break
    else:
        continue
    break
else:
    print(n_r_max + n_c_max - 1)

Submission status: Accepted

Solution code:
h,w,m=map(int, input().split())
r = [0]*max(h,w)
c = [0]*max(h,w)
l=[]

for i in range(m):
    x,y=map(int, input().split())
    r[x-1]+=1
    c[y-1]+=1
    l.append([x,y])

cm = max(c)
rm = max(r)
ci = [i for i, x in enumerate(c) if x == cm]
ri = [i for i, x in enumerate(r) if x == rm]
ans = cm + rm

cnt = 0
#print(l,ci,ri)
for i in range(m):
    if r[l[i][0]-1] == rm and c[l[i][1]-1] ==cm:
        cnt += 1

if cnt == len(ci)*len(ri):
    print(int(ans)-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[0 for i in range(h)]
R=[0 for i in range(w)]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G[i]=1
for i in range(w):
    if r[i]==e:
        R[i]=1
f=0
for i in range(m):
    p=0
    q=0
    x=a[i][0]
    y=a[i][1]
    if G[x-1]==1:
        p=1
    if R[y-1]==1:
        q=1


    if p==q==1:
        f+=1
v=1
if f!=G.count(1)*R.count(1):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)

Submission status: Accepted

Solution code:
H,W,M = [int(x) for x in input().split()]
hw = []
hNum = [0]*H
wNum = [0]*W

for i in range(M):
    h,w = [int(x) for x in input().split()]
    hw.append([h,w])
    hNum[h-1]+=1
    wNum[w-1]+=1

hmax = max(hNum)
hMaxList = []
wmax = max(wNum)
wMaxList = []

for i in range(H):
    if(hmax == hNum[i]):
        hMaxList.append(i)
for i in range(W):
    if(wmax == wNum[i]):
        wMaxList.append(i)

ans = wmax + hmax
count = 0
for i in hw:
    if(hNum[i[0]-1] == hmax and wNum[i[1]-1] == wmax):
        count += 1
if(hNum.count(hmax) * wNum.count(wmax) == count):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:

def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  P_X[k[0]] == Max_X and P_Y[k [1]] == Max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, sys.stdin.readline().split())
hlst = {}
wlst = {}
hwlst = []

for i in range(M):
    h, w = map(int, sys.stdin.readline().split())
    if h in hlst:
        hlst[h] += 1
    else:
        hlst[h] = 1

    if w in wlst:
        wlst[w] += 1
    else:
        wlst[w] = 1

    hwlst.append([h, w])

h = max(hlst.values())
w = max(wlst.values())
hmax = [i for i in hlst if hlst[i] == h]
wmax = [i for i in wlst if wlst[i] == w]
num = len(hmax)*len(wmax)


for i in hwlst:
    if hlst[i[0]] == h and wlst[i[1]] == w:
        num -= 1

if num:
    print(h+w)
else:
    print(h+w-1)

Submission status: Accepted

Solution code:
(h,w,m),*s=[[*map(int,i.split())]for i in open(0)]
r,c=[0]*-~h,[0]*-~w
for x,y in s:
    r[x]+=1
    c[y]+=1
print((R:=max(r))+(C:=max(c))-(r.count(R)*c.count(C)==sum(r[x]+c[y]==R+C for x,y in s)))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

h, w, m, *bomb = map(int, sys.stdin.buffer.read().split())
biii = bomb[0::2]
bjjj = bomb[1::2]
h_cnt = Counter(biii).most_common()
w_cnt = Counter(bjjj).most_common()

mi, mh = h_cnt[0]
h_idx = {mi}
for i, c in h_cnt[1:]:
    if c < mh:
        break
    h_idx.add(i)

mi, mw = w_cnt[0]
w_idx = {mi}
for i, c in w_cnt[1:]:
    if c < mw:
        break
    w_idx.add(i)

ans = mh + mw
cross_bomb = 0

for bi, bj in zip(biii, bjjj):
    if bi in h_idx and bj in w_idx:
        cross_bomb += 1

if len(h_idx) * len(w_idx) == cross_bomb:
    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if counter_h[h[i]]==MAX_h and counter_w[w[i]]==MAX_w:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, sys.stdin.readline().split())
hlst = {}
wlst = {}
hwlst = []

for i in range(M):
    h, w = sys.stdin.readline().split()
    if h in hlst:
        hlst[h] += 1
    else:
        hlst[h] = 1

    if w in wlst:
        wlst[w] += 1
    else:
        wlst[w] = 1

    hwlst.append([h, w])

h = max(hlst.values())
w = max(wlst.values())
hmax = [i for i in hlst if hlst[i] == h]
wmax = [i for i in wlst if wlst[i] == w]
num = len(hmax)*len(wmax)
ans = h + w -1


for i in hwlst:
    if hlst[i[0]] == h and wlst[i[1]] == w:
        num -= 1

if num == 0:
    print(ans)
else:
    print(ans+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

H,W,M=map(int,input().split())
hw = defaultdict(int)
sum1=[0]*H
sum2=[0]*W
for i in range(M):
  h,w=map(int,input().split())
  hw[(h-1,w-1)] += 1
  sum1[h-1] += 1
  sum2[w-1] += 1

sum1 = sorted(enumerate(sum1),key=lambda x:x[1],reverse=True)
sum2 = sorted(enumerate(sum2),key=lambda x:x[1],reverse=True)

max1,max2=set([sum1[0][0]]),set([sum2[0][0]])
for i in range(1,H):
  if sum1[i][1]<sum1[0][1]:
    break
  else:
    max1.add(sum1[i][0])
    
for i in range(1,W):
  if sum2[i][1]<sum2[0][1]:
    break
  else:
    max2.add(sum2[i][0])

ans = sum1[0][1]+sum2[0][1]
count=0
for k in hw.keys():
  h,w=k
  if h in max1 and w in max2:
    count += 1
    
if count < len(max1)*len(max2):
  print(ans)
else:
  print(ans-1)

Submission status: Accepted

Solution code:
import time

t0 = time.time()

h,w,m = map(int,input().split())
H = [0]*(h+1)
W = [0]*(w+1)
s = set([])
for i in range(m):
    a,b = map(int,input().split())
    s.add((a,b))

    H[a] += 1
    W[b] += 1

x = [0]*(h+1)
y = [0]*(w+1)
    
for i in range(h+1):
    x[i] = [i,H[i]]
for i in range(w+1):
    y[i] = [i,W[i]]

x.sort(key= lambda val : val[1],reverse=True)
y.sort(key= lambda val : val[1],reverse=True)

ma = x[0][1]
mb = y[0][1]

i,j = 0,0
sw = 0
while 1:
    if j > w:
        break
    if  x[i][1] == ma:
        if (x[i][0],y[j][0]) in s:
            pass
        else:
            if x[i][1]+y[j][1] == ma+mb:
                sw = 1
                break
        i += 1
    else:
        i = 0
        j += 1
    if time.time() - t0 > 2.5:
        break

    
print(ma+mb+sw-1)

Submission status: Accepted

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

from collections import defaultdict

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

cnt = defaultdict(int)
cnt_h = defaultdict(int)
cnt_w = defaultdict(int)

for h, w in hw:
    cnt[(h, w)] += 1
    cnt_h[h] += 1
    cnt_w[w] += 1
cnt_h = list(cnt_h.items())
cnt_w = list(cnt_w.items())
cnt_h.sort(key = lambda x: -x[1])
cnt_w.sort(key = lambda x: -x[1])

max_h = []
max_w = []
for h, n in cnt_h:
    if n == cnt_h[0][1]:
        max_h.append(h)
for w, n in cnt_w:
    if n == cnt_w[0][1]:
        max_w.append(w)

answer = cnt_h[0][1] + cnt_w[0][1]
for mh in max_h:
    for mw in max_w:
        if cnt[(mh, mw)] == 0:
            print(answer)
            exit()

print(answer - 1)

Submission status: Accepted

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

from collections import defaultdict

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

cnt = defaultdict(int)
cnt_h = defaultdict(int)
cnt_w = defaultdict(int)

for h, w in hw:
    cnt[(h, w)] += 1

for h, w in hw:
    cnt_h[h] += 1
    cnt_w[w] += 1
cnt_h = list(cnt_h.items())
cnt_w = list(cnt_w.items())
cnt_h.sort(key = lambda x: -x[1])
cnt_w.sort(key = lambda x: -x[1])

max_h = []
max_w = []
for h, n in cnt_h:
    if n == cnt_h[0][1]:
        max_h.append(h)
for w, n in cnt_w:
    if n == cnt_w[0][1]:
        max_w.append(w)

answer = cnt_h[0][1] + cnt_w[0][1]
for mh in max_h:
    for mw in max_w:
        if cnt[(mh, mw)] == 0:
            print(answer)
            exit()

print(answer - 1)

Submission status: Accepted

Solution code:
import sys
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxHCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxHCount]


maxWCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxWCount]

#counterList = []
#for maxH in maxHList:
#  for maxW in maxWList:
#    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
#print(max(counterList))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))

#if M < len(maxHList)*len(maxWList):
#	print(maxHCount + maxWCount)
#	sys.exit(0)

for maxH in maxHList:
  for maxW in maxWList:
    if (maxH, maxW) not in pList:
      print(maxHCount + maxWCount)
      sys.exit(0)

print(maxHCount + maxWCount - 1)

Submission status: Accepted

Solution code:
import sys


def main():
    h, w, m = map(int, input().split())
    row = [0]*h
    col = [0]*w
    bomb = set()
    for x in sys.stdin.readlines():
        H, W = map(int, x.split())
        bomb.add((H-1, W-1))
        row[H-1] += 1
        col[W-1] += 1

    maxrow = max(row)
    maxcol = max(col)
    ans = maxcol + maxrow - 1
    p, q = [], []
    for i in range(h):
        if row[i] == maxrow:
            p.append(i)
    for i in range(w):
        if col[i] == maxcol:
            q.append(i)

    for i in p:
        for j in q:
            if (i, j) not in bomb:
                print(ans + 1)
                exit()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

targets = []
n_target_h = [0] * H
n_target_w = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    targets.append((h, w))
    n_target_h[h - 1] += 1
    n_target_w[w - 1] += 1

h_max = max(n_target_h)
w_max = max(n_target_w)

bomb_h = [i + 1 for i, h in enumerate(n_target_h) if h == h_max]
bomb_w = [i + 1 for i, w in enumerate(n_target_w) if w == w_max]

count = len(bomb_h) * len(bomb_w)
for target in targets:
    if (n_target_h[target[0] - 1] == h_max) and (n_target_w[target[1] - 1] == w_max):
        count -= 1

if count > 0:
    ans = h_max + w_max
else:
    ans = h_max + w_max - 1

print(ans)

Submission status: Accepted

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

# 行、列ごとの爆破数
H = [0] * h
W = [0] * w

L = [(0, 0)] * m

for i in range(m):
    a, b = map(int, input().split())
    L[i] = (a, b)
    H[a-1] += 1
    W[b-1] += 1
h_max = max(H)
w_max = max(W)
ans = h_max + w_max

cnt = 0
for l in L:
    # 爆破対象のマスに爆弾を設置しているかの判定
    if H[l[0]-1] == h_max and W[l[1]-1] == w_max:
        cnt += 1
if H.count(h_max) * W.count(w_max) == cnt:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from sys import exit
H, W, m = map(int, input().split())
b_h = [[0, i] for i in range(H)]
b_w = [[0, i] for i in range(W)]
bs = set()
for _ in range(m):
	h, w = map(int, input().split())
	b_h[h-1][0] += 1
	b_w[w-1][0] += 1
	bs.add((h-1, w-1))

b_h.sort(reverse=True)
b_w.sort(reverse=True)
I = 0
while I < H-1 and b_h[I+1][0] == b_h[0][0]:
	I += 1

J = 0
while J < W-1 and b_w[J+1][0] == b_w[0][0]:
	J += 1

for i in range(I+1):
	for j in range(J+1):
		if (b_h[i][1], b_w[j][1]) not in bs:
			print(b_h[0][0] + b_w[0][0])
			exit()
print(b_h[0][0] + b_w[0][0] - 1)

Submission status: Accepted

Solution code:
import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = set()
for x in sys.stdin.readlines():
    H, W = map(int, x.split())
    bomb.add((H-1, W-1))
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)

for i in p:
    for j in q:
        if (i, j) not in bomb:
            print(ans + 1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
P = [0]*(H+1)
Q = [0]*(W+1)
A = set()
for k in range(M):
    a,b = map(int,input().split())
    P[a] += 1
    Q[b] += 1
    A.add((a,b))
Pmax = max(P)
Qmax = max(Q)
Pindex = []
Qindex = []
for i in range(H+1):
    if P[i] == Pmax:
        Pindex.append(i)
for i in range(W+1):
    if Q[i] == Qmax:
        Qindex.append(i)
ans = Pmax+Qmax-1
key = 0
for x in Pindex:
  for y in Qindex:
    if (x,y) not in A:
      ans += 1
      key = 1
      break
  if key == 1:
    break
print(ans)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
h,w,m=f()
l,H,W=[],[0]*-~h,[0]*-~w
for _ in range(m):
  x,y=f()
  l+=[(x,y)]
  H[x]+=1
  W[y]+=1
s,t=max(H),max(W)
print(s+t-(H.count(s)*W.count(t)==sum(H[x]+W[y]==s+t for x,y in l)))

Submission status: Accepted

Solution code:
import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = set([i+1 for i, h_ in enumerate(h_lst) if h_ == h_count])
w_cand = set([i+1 for i, w_ in enumerate(w_lst) if w_ == w_count])
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * M for i in range(2)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[0][i] = hi-1
    DST[1][i] = wi-1

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]

Hchk = [False]*H
Wchk = [False]*W
for i in Hbomb:
    Hchk[i] = True
for i in Wbomb:
    Wchk[i] = True

tmp = 0
for i in range(M):
    if Hchk[DST[0][i]] and Wchk[DST[1][i]]:
        tmp += 1

if len(Hbomb)*len(Wbomb) == tmp:
    print(Hdstmax + Wdstmax - 1)
else:
    print(Hdstmax + Wdstmax)