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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1

    my = max(ay)
    mx = max(ax)
    
    by = bx = 0
    for y in ay:
        if y == my:
            by += 1
    for x in ax:
        if x == mx:
            bx += 1
            
    ans = my + mx
    tmp = 0
    for x in s:
        if ay[x[0]]+ax[x[1]]==ans:
            tmp += 1
    if tmp == by*bx:
        ans -= 1
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H
Y = [0] * W
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = []
C = []
for h, x in enumerate(X):
    if x == maxX:
        R.append(h)
for w, y in enumerate(Y):
    if y == maxY:
        C.append(w)

if len(R) * len(C) > M:
    ans = maxX + maxY
else:
    done = set()
    for r in R:
        for c in C:
            done.add((r, c))
    for b in bomb:
        if b in done:
            done.remove(b)
    if len(done) > 0:
        ans = maxX + maxY
    else:
        ans = maxX + maxY - 1
print(ans)

Submission status: Accepted

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

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

H = []
W = []
for i in range(m):
    hh, ww = tuple(map(int, input().split()))
    H.append(hh)
    W.append(ww)
h_m = Counter(H).most_common()[0]
w_m = Counter(W).most_common()[0]

ans_1 = h_m[1]
ans_2 = w_m[1]

# print(ans_1, ans_2)
WW = []
HH = []
for i in range(m):
    if H[i] == h_m[0]:
        continue
    WW.append(W[i])

for i in range(m):
    if W[i] == w_m[0]:
        continue
    HH.append(H[i])
if WW:
    ans_1 += Counter(WW).most_common()[0][1]
if HH:
    ans_2 += Counter(HH).most_common()[0][1]

print(max(ans_1, ans_2))


# hw.sort()
# hw_rev = sorted(hw, key=lambda x: x[1])

# index_sum_h = []
# sum_h = []
# index = -1
# for i in hw:
#     a, b = i
#     if a == index:
#         index_sum_h[-1][1] += 1
#     else:
#         index = a
#         index_sum_h.append([a, 1])

# index_sum_w = []
# index = -1
# for i in hw_rev:
#     a, b = i
#     if b == index:
#         index_sum_w[-1][1] += 1
#     else:
#         index = b
#         index_sum_w.append([b, 1])

# # print(hw)
# # print(index_sum_h)
# # print(index_sum_w)

# index_sum_h = sorted(index_sum_h, key=lambda x: x[1], reverse=True)
# index_sum_w = sorted(index_sum_w, key=lambda x: x[1], reverse=True)

# # print(index_sum_h)
# # print(index_sum_w)
# dq = deque([[0, 0]])

# ans_tmp = index_sum_h[0][1]+index_sum_w[0][1]

# hw = set(hw)
# while len(dq) > 0:
#     index_h, index_w = dq.popleft()
#     a, b = index_sum_h[index_h]
#     c, d = index_sum_w[index_w]

#     # print([a, c])
#     # print([a, c] in hw)
#     if (a, c) in hw:
#         ans = ans_tmp-1
#         if index_h+1 < len(index_sum_h):
#             if index_sum_h[index_h+1][1] == b:
#                 dq.append([index_h+1, index_w])
#         if index_w+1 < len(index_sum_w):
#             if index_sum_w[index_w+1][1] == d:
#                 dq.append([index_h, index_w+1])

#     else:
#         print(b+d)
#         exit()

# print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)



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

INF=10**20
def solve(H: int, W: int, M: int, _h: "List[int]", _w: "List[int]"):
    H_count = [0] * (H+1)
    W_count = [0] * (W+1)
    G = set()
    seenH = set()
    seenW = set()
    for i in range(M):
        h,w=_h[i],_w[i]
        H_count[h] += 1
        W_count[w] += 1
 
        seenH.add(h)
        seenW.add(w)
        G.add((h,w))
    
    Hs = []
    Ws = []
    for i in range(max(H,W)+1):
        if i < len(H_count):
            count = H_count[i]
            if count > 0:
                Hs.append((count,i))
 
        if i < len(W_count):
            count = W_count[i]
            if count > 0:
                Ws.append((count,i))
 
 
    Hs.sort(reverse=True)
    Ws.sort(reverse=True)
 
    # print(Hs)
    # print(Ws)
 
    h_count,h = Hs[0]
    w_count,w = Ws[0]
 
    original = h_count + w_count
    ans = original
    if (h,w) in G:
        # print("a")
        ans -= 1
 
        i = 1
        sameH = []
        while i < len(Hs) and Hs[i][0] == h_count:
            # print("h")
            h = Hs[i][1]
            i += 1
            sameH.append(h)
        
        i = 1
        sameW = []    
        while i < len(Ws) and Ws[i][0] == w_count:
            w = Ws[i][1]
            i += 1
            sameW.append(w)
           
        max_mass = (len(sameH)+1) * (len(sameW)+1)
 
        # print(max_mass)
        on_bom_count = 0
        for h,w in G:
            count = H_count[h] + W_count[w]
            if count == original:
                on_bom_count += 1
        
        if max_mass - on_bom_count > 0:
            ans += 1
 
                
    print(ans)
    return

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 sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]
 
gh = {i:{} for i in range(h)}
gw = {i:{} for i in range(w)}
 
for _h, _w in hw:
    gh[_h-1][_w-1]=_w-1
    gw[_w-1][_h-1]=_h-1
    
ansh = 0
posh = {}
answ = 0
posw = {}
for k,v in gh.items():
    if len(v) > ansh:
        ansh = len(v)
        
for k,v in gh.items():
    if len(v) == ansh:
        posh[k]=k
        
for k,v in gw.items():
    if len(v) > answ:
        answ = len(v)
        
for k,v in gw.items():
    if len(v) == answ:
        posw[k]=k
        
hoge = True
for i in posh:
    for j in posw:
        if i not in gw[j]:
            hoge = False
            break
            
if hoge:
    print(ansh+answ-1)
else:
    print(ansh+answ)

Submission status: Accepted

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

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
        
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            break
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)

Submission status: Accepted

Solution code:
import numpy as np

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

x_list = [0 for i in range(w)]
y_list = [0 for i in range(h)]

target = [set() for i in range(h)]

for i in range(m):
    hi, wi = map(int, input().split())
    y_list[hi-1] += 1
    x_list[wi-1] += 1
    target[hi-1].add(wi-1)


y_max = max(y_list)
y_max_list = np.where(np.array(y_list) == y_max)[0]
x_max = max(x_list)
x_max_list = np.where(np.array(x_list) == x_max)[0]

minus = True

for y in y_max_list:
    for x in x_max_list:
        if x in target[y]:
            continue
        else:
            minus = False
            break

if minus:
    print(y_max + x_max - 1)
else:
    print(y_max + x_max)

Submission status: Accepted

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

for i in range(m):
    h1,w1=list(map(int,input().split()))
    table.append((h1-1,w1-1))
    H[h1-1]+=1
    W[w1-1]+=1

h_flag=0
w_flag=0

Hm=max(H)
Wm=max(W)

Hh=[i for i, x in enumerate(H) if x == Hm]
Ww=[i for i, x in enumerate(W) if x == Wm]

cnt=0

for (h, w) in table:
    if H[h] == Hm and W[w] ==  Wm:
        cnt += 1

if cnt<len(Hh)*len(Ww):
    print(Hm+Wm)
else:
    print(Hm+Wm-1)

Submission status: Accepted

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

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)

Submission status: Accepted

Solution code:
import sys, math, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for j in ys:

        bombs[j].sort()
        for i in xs:
            index = bisect.bisect_left(bombs[j], i)
            if(index == V_N[j] or i != bombs[j][index]):
                return value
            
    return value-1



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )


    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)




    print( solve(W_N, V_N, bombs, H, W) )

Submission status: Accepted

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

hmax = max(hlist)
wmax = max(wlist)
hmaxlist = [i for i, v in enumerate(hlist) if v == hmax]
wmaxlist = [i for i, v in enumerate(wlist) if v == wmax]
cnt = -1
for i in hmaxlist:
    bf = False
    for j in wmaxlist:
        if not (i, j) in hw:
            cnt = 0
            bf = True
            break
    if bf:
        break

print(hmax + wmax + cnt)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH, PW = [], []
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PF[h, w] += 1

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()

most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = [x[0] for x in frequency_h_list if x[1] == most_common_h_cnt]
most_common_w_list = [x[0] for x in frequency_w_list if x[1] == most_common_w_cnt]

diff = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            diff = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + diff

print(cnt)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
H=[0 for i in range(h)]
W=[0 for i in range(w)]
s=set()
for i in range(m):
    a,b=map(int,input().split())
    H[a-1]+=1
    W[b-1]+=1
    s.add((a,b))
hma=max(H)
wma=max(W)
h_index=[x for x, v in enumerate(H) if v==hma]
w_index=[y for y, v in enumerate(W) if v==wma]
val=-1
for p in h_index:
    for q in w_index:
        if not (p+1,q+1) in s:
            val=0
            break
print(hma+wma+val)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
l = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
A,B,ans = [0]*h,[0]*w,0
for i, j in l:
    A[i] += 1;    B[j] += 1 
ma,mb = max(A),max(B)
count = A.count(ma)*B.count(mb)
for i, j in l:
    if A[i] == ma and B[j] == mb:
        count -= 1
print(ma+mb-1 if count == 0 else ma+mb)

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m,t=map(int,input().split())
    dr=defaultdict(list)
    dc=defaultdict(list)
    mx=0
    for i in range(t):
        a,b=map(int,input().split())
        dr[a].append((a,b))
        mx=max(len(dr[a]),mx)
        dc[b].append((a,b))

    d=defaultdict(int)

    for i in dr.keys():
        if(len(dr[i])==mx):
            d[i]=True
    ans=0
    for i in dc.keys():
        ct=0
        for j,k in dc[i]:
            if(j in d):
                ct+=1
        if(ct<len(d)):
            ans=max(ans,mx+len(dc[i]))
        else:
            ans = max(ans, mx + len(dc[i])-1)
    print(ans)








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:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PF[h, w] += 1

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()
most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = []
for x in frequency_h_list:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in frequency_w_list:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
d=dict()
s=set()
a=[0]*h
b=[0]*w
for _ in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  a[x]+=1
  b[y]+=1
  d[x*10**6+y]=1
  s.add(x*10**6+y)

ma=max(a)
mb=max(b)

ind_x=[i for i,j in enumerate(a) if j==ma]
ind_y=[i for i,j in enumerate(b) if j==mb]


for x in ind_x:
  for y in ind_y:
    if not(x*10**6+y in s):
      print(ma+mb)
      exit()
print(ma+mb-1)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PHF = defaultdict(int)
PWF = defaultdict(int)
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PHF[h] += 1
    PWF[w] += 1
    PF[h, w] += 1

sorted_PHF = sorted(PHF.items(), key=lambda x: x[1], reverse=True)
sorted_PWF = sorted(PWF.items(), key=lambda x: x[1], reverse=True)
most_common_h_cnt = sorted_PHF[0][1]
most_common_w_cnt = sorted_PWF[0][1]

most_common_h_list = []
for x in sorted_PHF:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in sorted_PWF:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
d=dict()
a=[0]*h
b=[0]*w
for _ in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  a[x]+=1
  b[y]+=1
  d[x*10**6+y]=1

ma=max(a)
mb=max(b)

ind_x=[i for i,j in enumerate(a) if j==ma]
ind_y=[i for i,j in enumerate(b) if j==mb]


for x in ind_x:
  for y in ind_y:
    if not(x*10**6+y in d):
      print(ma+mb)
      exit()
print(ma+mb-1)

Submission status: Accepted

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

hh = [[0,_] for _ in range(H+1)]
ww = [[0,_] for _ in range(W+1)]

#hh = [0]*(H+1)
#ww = [0]*(W+1)
d = {}

for i in range(M):
    h,w = map(int,input().split())
    hh[h][0] += 1
    ww[w][0] += 1
    d[(h,w)] = True

bomb = []
for kh,kw in d.keys():
    bomb.append(hh[kh][0] + ww[kw][0] -1)
bombMax = max(bomb)

hh.sort(reverse=True)
ww.sort(reverse=True)
Mh = hh[0][0]
Mw = ww[0][0]
maxh = []
maxw = []
for i in range(H):
    if hh[i][0] == Mh:
        maxh.append(hh[i][1])
    else:
        break
for i in range(W):
    if ww[i][0] == Mw:
        maxw.append(ww[i][1])
    else:
        break

for h in maxh:
    for w in maxw:
        if (h,w) not in d:
            print(Mh+Mw)
            break
    else:
        continue
    break
else:
    print(Mh+Mw-1)
"""
print(maxh)
print(maxw)
print(d)
print(bomb)
"""

Submission status: Accepted

Solution code:
from collections import*
h,w,m=map(int,input().split())
d=defaultdict(int)
a=[0]*h
b=[0]*w
for _ in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  a[x]+=1
  b[y]+=1
  d[x*10**6+y]+=1

ma=max(a)
mb=max(b)

ind_x=[i for i,j in enumerate(a) if j==ma]
ind_y=[i for i,j in enumerate(b) if j==mb]


for x in ind_x:
  for y in ind_y:
    if d[x*10**6+y]==0:
      print(ma+mb)
      exit()
print(ma+mb-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
R = [0] * h
C = [0] * w
XY = [tuple(map(lambda x:int(x) - 1, input().split())) for i in range(m)]
for x, y in XY:
    R[x] += 1
    C[y] += 1
maxR, maxC = max(R), max(C)
cnt0 = R.count(maxR) * C.count(maxC)
cnt1 = sum(R[x] == maxR and C[y] == maxC for x, y in XY)
print(maxR + maxC - int(cnt0 == cnt1))

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
R = [0] * h
C = [0] * w
XY = [tuple(map(int, input().split())) for i in range(m)]
X = [x - 1 for x, y in XY]
Y = [y - 1 for x, y in XY]
for x, y in zip(X, Y):
    R[x] += 1
    C[y] += 1
maxR, maxC = max(R), max(C)
cnt0 = R.count(maxR) * C.count(maxC)
cnt1 = 0
for x, y in zip(X, Y):
    if R[x] == maxR and C[y] == maxC:
        cnt1 += 1
print(maxR + maxC - int(cnt0 == cnt1))

Submission status: Accepted

Solution code:
from collections import*
h,w,m=map(int,input().split())
d=defaultdict(int)
a=[0]*h
b=[0]*w
for _ in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  a[x]+=1
  b[y]+=1
  d[(x,y)]+=1

ma=max(a)
mb=max(b)

ind_x=[i for i,j in enumerate(a) if j==ma]
ind_y=[i for i,j in enumerate(b) if j==mb]


for x in ind_x:
  for y in ind_y:
    if d[(x,y)]==0:
      print(ma+mb)
      exit()
print(ma+mb-1)

Submission status: Accepted

Solution code:
import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

h = [-1]
w = [-1]
hw_dict = defaultdict(int)

for _ in range(M):
    hi, wi = map(int, input().split())
    h.append(hi)
    w.append(wi)
    hw_dict[(hi, wi)] = 1

h_cnt = [0] * (H + 1)
w_cnt = [0] * (W + 1)

for i in range(1, M + 1):
    h_cnt[h[i]] += 1
    w_cnt[w[i]] += 1

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

h_max_idx = []
w_max_idx = []

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

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

ans = 0

for i in h_max_idx:
    for j in w_max_idx:
        if hw_dict[(i, j)] == 0:
            print(h_max + w_max)
            exit()

print(h_max + w_max - 1)

Submission status: Accepted

Solution code:
H, W, M = [int(n) for n in input().split()]
H_freq = [0] * H
W_freq = [0] * W

table = []
for m in range(M):
    h, w = [int(n)-1 for n in input().split()]
    H_freq[h] += 1
    W_freq[w] += 1
    table.append((h, w))

max_h = max(H_freq)
max_w = max(W_freq)
most_freqent_h = [i for i, h in enumerate(H_freq) if h == max_h]
most_freqent_w = [i for i, w in enumerate(W_freq) if w == max_w]

count = 0
for (h, w) in table:
    if H_freq[h] == max_h and W_freq[w] == max_w:
        count += 1

if count < len(most_freqent_h) * len(most_freqent_w):
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W, M = map(int, input().split())
    lh = [0] * H
    lw = [0] * W
    ll = []
    for _ in range(M):
        h, w = map(int, input().split())
        lh[h - 1] += 1
        lw[w - 1] += 1
        ll.append((h - 1, w - 1))

    maxh = max(lh)
    maxw = max(lw)
    wlist = []


    # for i in range(H):
    #     if lh[i] != maxh:
    #         continue
    #     for j in wlist:
    #         if (i, j) not in s:
    #             print(maxh + maxw)
    #             exit()
    count = lh.count(maxh) * lw.count(maxw)
    for h, w in ll:
        if lh[h] == maxh and lw[w] == maxw:
            count -= 1

    if count:
        print(maxh + maxw)
    else:
        print(maxh + maxw - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

r,c,m=map(int,input().split())
q=set(tuple(map(lambda x :int(x)-1,input().split())) for _ in range(m))
rows = [0]*r
cols = [0]*c

for i,j in q:
    rows[i]+=1
    cols[j]+=1

MAXR = max(rows)
MAXC = max(cols)

ans = MAXR+MAXC-1

rlist=[]
clist=[]

for i in range(r):
    if rows[i]==MAXR:
        rlist.append(i)

for j in range(c):
    if cols[j]==MAXC:
        clist.append(j)
   
for i in rlist:
    for j in clist:
        if (i,j) in q:
            continue
        else:
            ans+=1
            print(ans)
            sys.exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

    maxh = max(lh)
    maxw = max(lw)
    wlist=[]
    for j in range(W):
        if maxw==lw[j]:
            wlist.append(j)



    for i in range(H):
        if lh[i] !=maxh:
            continue
        for j in wlist:
            if (i,j) not in s:
                print(maxh+maxw)
                exit()

    print(maxh+maxw-1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import groupby


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(ll):
    return sum(1 for _ in ll)


def solve():
    H, W, M = read_ints()
    hw = []
    for _ in range(M):
        hw.append(tuple(read_ints()))
    hw.sort()

    rows = set()
    max_count_row = 0
    for h, ws in groupby(hw, key=lambda pair: pair[0]):
        count = ilen(ws)
        if count == max_count_row:
            rows.add(h)
        elif count > max_count_row:
            rows = set([h])
            max_count_row = count

    hw.sort(key=lambda pair: pair[1])
    cols = set()
    max_count_col = 0
    for w, hs in groupby(hw, key=lambda pair: pair[1]):
        count = ilen(hs)
        if count == max_count_col:
            cols.add(w)
        elif count > max_count_col:
            cols = set([w])
            max_count_col = count

    hw = set(hw)
    for h in rows:
        for w in cols:
            if (h, w) not in hw:
                return max_count_row+max_count_col
    return max_count_row+max_count_col-1


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: Set[int] = set()
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.add(item)
        # codList.setdefault(h, {})
        # codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row + 1, column + 1) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = set()
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.add(item)
        # codList.setdefault(h, {})
        # codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row + 1, column + 1) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()