Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

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

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

1 \leq h_i \leq H

1 \leq w_i \leq W

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

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

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

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

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

Sample Output 3

6



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


Sample output:
3

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w, m = map(int, readline().split())
    row = [0] * h
    col = [0] * w
    target = [[] for _ in range(h)]

    for _ in range(m):
        ch, cw = map(int, readline().split())
        ch, cw = ch - 1, cw - 1
        row[ch] += 1
        col[cw] += 1
        target[ch].append(cw)

    ans = 0
    c_max = max(col)
    max_cnt = col.count(c_max)

    for r in range(h):
        cnt_r = row[r]
        cnt_c = c_max
        rem = max_cnt
        for c in target[r]:
            if col[c] == c_max:
                rem -= 1
        if rem > 0:
            ans = max(ans, cnt_r + cnt_c)
        else:
            ans = max(ans, cnt_r + cnt_c - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 6

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 * INF + w] += 1
#print(cnt)

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])
#print(cnt_h)
#print(cnt_w)

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)
#print(max_h)
#print(max_w)

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

Submission status: Accepted

Solution code:
from itertools import product
h, w, m = map(int, input().split())


row = [set()for _ in range(h)]
col = [set()for _ in range(w)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    row[x].add(y)
    col[y].add(x)

crow = 0
ic = []
for i, x in enumerate(row):
    if crow < len(x):
        crow = len(x)
        ic = [i]
    elif crow == len(x):
        ic.append(i)

ccol = 0
jc = []
for j, x in enumerate(col):
    if ccol < len(x):
        ccol = len(x)
        jc = [j]
    elif ccol == len(x):
        jc.append(j)


ans = crow+ccol
for i, j in product(ic, jc):
    if j not in row[i]:
        print(ans)
        break
else:
    print(ans-1)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
hw = {tuple(map(int,input().split())) for _ in [0]*M}

INF = 3*10**5+10
H_cnt = [0]*INF
W_cnt = [0]*INF
for h,w in hw:
    H_cnt[h] += 1
    W_cnt[w] += 1

H_cnt = sorted(enumerate(H_cnt),key = lambda x:-x[1])
W_cnt = sorted(enumerate(W_cnt),key = lambda x:-x[1])

h1,nh1 = H_cnt[0]
w1,nw1 = W_cnt[0]
H_ans = [hi for hi,nhi in H_cnt if nhi == nh1]
W_ans = [wi for wi,nwi in W_cnt if nwi == nw1]
ans = nh1+nw1 - 1
if len(H_ans)*len(W_ans) >= INF:
    ans += 1
else:
    breakFlg = False
    for h in H_ans:
        for w in W_ans:
            if not ((h,w) in hw):
                ans += 1
                breakFlg = True
                break
        if breakFlg: break
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w,m = map(int,readline().split())
xy = [tuple(map(lambda x: int(x)-1,readline().split())) for _ in range(m)]
dic = set(xy)


hnum = [0]*h
wnum = [0]*w

for x,y in xy:
    hnum[x] += 1
    wnum[y] += 1
    
hmax = max(hnum)    
wmax = max(wnum)

hn = [i for i in range(h) if hnum[i]==hmax]
wn = [i for i in range(w) if wnum[i]==wmax]


d = 1
if len(hn)*len(wn) > m:
    d = 0
else:
    for i in hn:
        for j in wn:
            if (i,j) not in dic:
                d = 0
                break


#print(dic)

print(hmax+wmax-d)

Submission status: Accepted

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

h, w, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
CC = [[] for i in range(h)]
for i in range(m):
    CC[C[i][0]-1].append(C[i][1]-1)

for i in range(h):
    CC[i].sort()

A = [0] * h
B = [0] * w
for i in range(m):
    A[C[i][0]-1] += 1
    B[C[i][1]-1] += 1

# ans = 0
# for i in range(m):
#     ans = max(ans, A[C[i][0]-1] + B[C[i][1]-1] - 1)

D = [[A[i], i] for i in range(h)]
E = [[B[i], i] for i in range(w)]
D.sort(reverse=True)
E.sort(reverse=True)

# print(D,E)

from bisect import bisect
if not ([D[0][1]+1, E[0][1]+1] in C):
    # print("r1")
    ans = D[0][0] + E[0][0]
else:
    ans = 0
    aa = D[0][0] + E[0][0]
    co = 0
    F = []

    for i in range(h):
        for j in range(w):
            if D[i][0] + E[j][0] == aa:
                F.append([D[i][1], E[j][1]])
                co += 1
            else:
                break
        if co > m:
            break
    if co > m:
        # print("r2")
        ans = D[0][0] + E[0][0]
    else:
        ha = 0
        # print(F)
        # print(CC)
        for i in range(len(F)):
            ind = bisect(CC[F[i][0]], F[i][1])
            if ind==0 or (ind >= 1 and CC[F[i][0]][ind-1] != F[i][1]):
                # print(CC[ind-1], F[i][1])
                ha = 1
                break
        if ha == 1:
            # print("r3")
            ans = D[0][0] + E[0][0]
        else:
            # print("m1")
            ans = D[0][0] + E[0][0] - 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque

R, C, M = [int(x) for x in input().split()]
targets = [tuple(int(x) - 1 for x in input().split()) for i in range(M)]  # 0 indexed

if False:
    # Answer should be 4, not 3
    targets = [
        (0, 0),
        (0, 2),
        (1, 2),
        (2, 0),
        (2, 1),
    ]

mostByRow = Counter(r for r, c in targets)
mostByCol = Counter(c for r, c in targets)

r = max(mostByRow.keys(), key=lambda r: mostByRow[r])
c = max(mostByCol.keys(), key=lambda c: mostByCol[c])
ans = mostByRow[r] + mostByCol[c]
intersectsTarget = False
if (r, c) in targets:
    intersectsTarget = True
    ans -= 1
if intersectsTarget:
    maxR = max(mostByRow.values())
    maxC = max(mostByCol.values())

    rs = set(r for r, v in mostByRow.items() if v == maxR)
    cs = set(r for r, v in mostByCol.items() if v == maxC)

    points = 0
    for r, c in targets:
        if r in rs and c in cs:
            points += 1
    if points < len(rs) * len(cs):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
d = defaultdict(int)
tate = [0 for i in range(H+1)]
yoko = [0 for i in range(W+1)]
for i in range(M):
    x, y = map(int, input().split())
    d[(x, y)] = 1
    tate[x] += 1
    yoko[y] += 1

ans = 0
T = []
Y = []
for i, v in enumerate(tate):
    T.append((v, i))
for i, v in enumerate(yoko):
    Y.append((v, i))
T.sort(reverse=True)
Y.sort(reverse=True)

value_t = T[0][0]
value_y = Y[0][0]
cnt_t = 0
cnt_y = 0
for value, index in T:
    if value == value_t:
        cnt_t += 1

for Value, Index in Y:
    if Value == value_y:
        cnt_y += 1
if cnt_t*cnt_y > M:
    print(value_t+value_y)

else:
    M = T[0][0]+Y[0][0] - 1
    value_t = T[0][0]
    value_y = Y[0][0]
    for value, index in T:
        if value < value_t:
            break
        for Value, Index in Y:
            if Value < value_y:
                break
            if (index, Index) in d.keys():
                ans = max(ans, value+Value-1)
            else:
                ans = max(ans, value+Value)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy as copy
input = sys.stdin.readline


def main():
    h, w, m = map(int, input().split())
    
    bomb_h = [0]*h
    bomb_w = [0]*w
    bomb_w_place = [set() for _ in range(w)]
    for i in range(m):
        x, y = map(int, input().split())
        bomb_h[x-1] += 1
        bomb_w[y-1] += 1
        bomb_w_place[y-1].add(x-1)
    bomb_h2 = [0]*h
    for i in range(h):
        bomb_h2[i] = [bomb_h[i], i]
    bomb_h2.sort(reverse=True)
    
    ans = 0
    for i in range(w):
        index = 0
        key = bomb_w[i]
        k1, k2 = True, True
        ma = -1
        while index < len(bomb_h2):
            key2 = bomb_h2[index]
            if key2[1] in bomb_w_place[i]:
                if ma == -1:
                    ma = key2[0]-1
                    index += 1
                    continue
                elif ma == key2[0]-1:
                    index += 1
                    continue
                else:
                    break
            else:
                ma = max(ma, key2[0])
                break
            index += 1
        
        ans = max(ans, key+ma)
    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

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

x_num = [0] * (H+1)
y_num = [0] * (W+1)

it = iter(hw)
for h,w in zip(it,it):
    x_num[h] += 1
    y_num[w] += 1

x_max = max(x_num)
y_max = max(y_num)

x_max_set = set()
y_max_set = set()
for i,num in enumerate(x_num):
    if(num == x_max):
        x_max_set.add(i)

for i,num in enumerate(y_num):
    if(num == y_max):
        y_max_set.add(i)

cnt = 0
it = iter(hw)
for h,w in zip(it,it):
    if(h in x_max_set)&(w in y_max_set):
        cnt += 1

point = len(x_max_set) * len(y_max_set)
ans = x_max+y_max
if(point == cnt):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
test = [[i, i] for i in range(1, M+1)]
tH, tW, tag = [0]*H, [0]*W, set()
Hmax, Wmax = 0, 0

for _ in range(M):
    h, w = map(int, input().split())
    tH[h-1] += 1
    tW[w-1] += 1
    tag.add(W*(h-1) + (w-1))
    Hmax = max(Hmax, tH[h-1])
    Wmax = max(Wmax, tW[w-1])

Hind = [i for i, x in enumerate(tH) if x == Hmax]
Wind = [i for i, x in enumerate(tW) if x == Wmax]
if len(Hind) * len(Wind) > M:
    print(Hmax + Wmax)
    exit()
else:
    for h in Hind:
        for w in Wind:
            if W*h + w not in tag:
                print(Hmax + Wmax)
                exit()
print(Hmax + Wmax - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    H, W, M = map( int, input().split())
    HW = [ tuple( map( int, input().split())) for _ in range(M)]
    R = [0]*H
    C = [0]*W
    d = defaultdict( lambda : False)
    for h, w in HW:
        R[h-1] += 1
        C[w-1] += 1
        d[(h-1,w-1)] = True
    MR = max(R)
    MC = max(C)
    ans = MR+MC-1
    NR = []
    NC = []
    for index, r in enumerate(R):
        if r == MR:
            NR.append(index)
    for index, c in enumerate(C):
        if c == MC:
            NC.append(index)
    # print(NR)
    # print(NC)
    # print(ans,d)
    for r in NR:
        for c in NC:
            if not d[(r,c)]:
                # print(r,c)
                print(ans+1)
                return
    print(ans)
    # 自身を除く
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    21st AUGUST , 2020  - FRIDAY
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
@iterative
def dfs(v,visited,st,new):
    new.append(st)
    visited[st] = 1
    for i in v[st]:
        if(visited[i] == 0):
            ok = yield dfs(v,visited,i,new)
    yield True


def solve():
    n,m,p = sep()

    row = [0]*n
    col = [0]*m
    have = {}
    for i in range(p):
        a,b = sep()
        a-=1
        b-=1
        have[str(a)+' '+str(b)] = 1
        row[a] +=1
        col[b] +=1

    rmx = max(row)
    cmx = max(col)
    total = row.count(rmx)*col.count(cmx)
    ans = 0
    for i in have:
        ind = i.index(' ')
        a = int(i[:ind])
        b = int(i[ind+1:])
        if(row[a]==rmx and col[b] == cmx):
            ans +=1

    if(total==ans):
        print(rmx+cmx-1)
    else:
        print(rmx+cmx)










testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    h, w, m = map(int, input().split())
    h = [0] * m
    w = [0] * m
    object_set = set()
    for i in range(m):
        h[i], w[i] = map(int, input().split())
        object_set.add((h[i], w[i]))
    h_counter = Counter(h)
    w_counter = Counter(w)
    max_h_num = h_counter.most_common()[0][1]
    max_w_num = w_counter.most_common()[0][1]
    ans = max_h_num + max_w_num

    h_cand = set()
    w_cand = set()
    for e, n in h_counter.most_common():
        if n == max_h_num:
            h_cand.add(e)
    for e, n in w_counter.most_common():
        if n == max_w_num:
            w_cand.add(e)

    cnt = 0
    for h_e, w_e in object_set:
        if h_e in h_cand and w_e in w_cand:
            cnt += 1

    print(ans if cnt < len(h_cand) * len(w_cand) else ans - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def argmaxs(lst):
    mx=max(lst)
    output=[]
    for i,a in enumerate(lst):
        if a==mx:
            output.append(i)
    
    return output
    
def main():
    import sys
    H,W,M=list(map(int,sys.stdin.readline().split()))
    y_lst=[0]*H
    x_lst=[0]*W
    bumbs=[set() for _ in range(H)]

    for i in range(M):
        h,w=list(map(int,sys.stdin.readline().split()))
        y_lst[h-1]+=1
        x_lst[w-1]+=1
        bumbs[h-1].add(w-1)

    output=max(x_lst)+max(y_lst)
    
    
    argys=argmaxs(y_lst)
    argxs=argmaxs(x_lst)
    argx_set=set(argxs)

    k=1
    for y in argys:
        if not(argx_set <= bumbs[y]):
            k=0
            break

    
    print(output-k)
main()

Submission status: Accepted

Solution code:
def f():
    for i in R:
        for j in C:
            try:
                if d[(i,j)]:
                    pass
            except:
                return 1
    return 0

h,w,m=map(int,input().split())
r=[0 for i in range(h)]
c=[0 for i in range(w)]
t=[]
d={}
for i in range(m):
    x,y=map(int,input().split())
    d[(x-1,y-1)]=True
    r[x-1]+=1
    c[y-1]+=1
r_=max(r)
c_=max(c)
R=[]
C=[]
for i in range(h):
    if r[i]==r_:
        R.append(i)
for i in range(w):
    if c[i]==c_:
        C.append(i)

flag=f()
if flag:
    print(r_+c_)
else:
    print(r_+c_-1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w,m = LI()
    fx = [0]*w
    fy = [0]*h
    f = defaultdict(lambda : 0)
    for _ in range(m):
        y,x = LI()
        y -= 1
        x -= 1
        f[(y,x)] = 1
        fx[x] += 1
        fy[y] += 1
    m = 0
    lisx = []
    for x in range(w):
        srx = fx[x]
        if m < srx:
            m = srx
    for x in range(w):
        srx = fx[x]
        if m == srx:
            lisx.append(x)
    M = 0
    lisy = []
    for y in range(h):
        srx = fy[y]
        if M < srx:
            M = srx
    for y in range(h):
        srx = fy[y]
        if M == srx:
            lisy.append(y)
    ans = m+M
    for y in lisy:
        for x in lisx:
            if not f[(y,x)]:
                print(ans)
                return
    print(ans-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
A=[0 for i in range(H+1)]
B=[0 for i in range(W+1)]
N=[]
for i in range(M):
    h,w=map(int,input().split())
    A[h]+=1
    B[w]+=1
    N.append([h,w])
max_A=[]
max_value_A=0
for i in range(1,len(A)):
    if A[i]>max_value_A:
        max_value_A=A[i]
        max_A=[i]                   
    elif A[i]==max_value_A:
        max_A.append(i)
maxA=[0 for i in range(len(A))]
for i in max_A:
    maxA[i]+=1
max_B=[]
max_value_B=0
for j in range(1,len(B)):
    if B[j]>max_value_B:
        max_value_B=B[j]
        max_B=[j]
    elif B[j]==max_value_B:
        max_B.append(j)
maxB=[0 for i in range(len(B))]
for j in max_B:
    maxB[j]+=1
count=0
for i,j in N:
    if maxA[i]==1 and maxB[j]==1:
        count+=1
flag=0
if count==len(max_A)*len(max_B):
    flag=1
print(max_value_A+max_value_B-flag)

Submission status: Accepted

Solution code:
import collections as cc
import sys
import bisect as bi
I=lambda:list(map(int,input().split()))
a,b,m=I()
ar=[I() for i in range(m)]
row=cc.defaultdict(int)
col=cc.defaultdict(int)
rr=cc.defaultdict(int)
ccc=cc.defaultdict(int)
for i in ar:
	rr[i[0]]+=1
	ccc[i[1]]+=1
	row[tuple(i)]=1
rc=max(rr.values())
cr=max(ccc.values())
p=[i for i in rr if rr[i]==rc]
q=[i for i in ccc if ccc[i]==cr]
ans=rc+cr
tf=0
for i in p:
	for j in q:
		if row[(i,j)]==0:
			tf=1
			break
	if tf:
		break
if tf==0:
	ans-=1
print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
target = [tuple(map(lambda x:int(x) - 1, input().split())) for _ in range(M)]

X = [0 for _ in range(H)]
Y = [0 for _ in range(W)]

for i in range(M):
    h, w = target[i]
    X[h] += 1
    Y[w] += 1

xmax = max(X)
ymax = max(Y)

xlist = set()
ylist = set()

for i in range(H):
    if X[i] == xmax:
        xlist.add(i)

for i in range(W):
    if Y[i] == ymax:
        ylist.add(i)

tmp = 0

for h, w in target:
    if h in xlist and w in ylist:
        tmp += 1

if len(xlist) * len(ylist) == tmp:
    print(xmax + ymax - 1)
else:
    print(xmax + ymax)

Submission status: Accepted

Solution code:
import heapq
def main():
    H, W, M = map(int, input().split())

    bn_h = {}
    bn_v = {}

    for i in range(M):
        h, w = map(int, input().split())
        bn_h.setdefault(h, set())
        bn_h[h].add(w)
        bn_v.setdefault(w, set())
        bn_v[w].add(h)

    b1 = sorted(bn_h.items(), key = lambda x:len(x[1]), reverse=True)
    b2 = sorted(bn_v.items(), key = lambda x:len(x[1]), reverse=True)

    m1 = len(b1[0][1])
    m2 = len(b2[0][1])

    flag = False
    max_result = 0
    for i in b1:
        h, sh = i
        if len(sh) < m1:
            break
        for j in b2:
            v, sv = j
            if len(sv) < m2:
                break
            result = len(sh) + len(sv) - 1
            if h not in sv:
                result += 1
                flag = True
            max_result = max(max_result, result)
            if flag == True:
                break
        if flag == True:
            break
    print(max_result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dh = {}
dw = {}
for i in range(M):
    h,w = hw[i]
    if h not in dh:
        dh[h] = 0
    dh[h] += 1
    if w not in dw:
        dw[w] = 0
    dw[w] += 1

mh = 0
mw = 0
for h in dh:
    mh = max(mh,dh[h])
hcand = []
for h in dh:
    if dh[h]==mh:
        hcand.append(h)

for w in dw:
    mw = max(mw,dw[w])
wcand = []
for w in dw:
    if dw[w]==mw:
        wcand.append(w)

n_cand = len(hcand)*len(wcand)
for i in range(M):
    h,w = hw[i]
    if dh[h]==mh and dw[w]==mw:
        n_cand -= 1

if n_cand>0:
    ans = mh+mw
else:
    ans = mh+mw-1

print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hk = [[0, i] for i in range(H + 1)]
wk = [[0, j] for j in range(W + 1)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    hk[h][0] += 1
    wk[w][0] += 1
    s.add((h, w))
hk.sort(reverse=True)
wk.sort(reverse=True)
colmax = wk[0][0]
ans = 0
for lowacc, i in hk:
    if lowacc + colmax <= ans:
        break
    for colacc, j in wk:
        if lowacc + colacc <= ans:
            break
        else:
            ans = max(ans, lowacc + colacc - ((i, j) in s))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hs = defaultdict(int)
ws = defaultdict(int)
expl = set()

for i in range(M):
    h, w = map(int, input().split())
    hs[h] += 1
    ws[w] += 1
    expl.add((h, w))

hscan = []
wscan = []
hmax = max(hs.values())
wmax = max(ws.values())

for i, m in hs.items():
    if m == hmax:
        hscan.append(i)

for i, m in ws.items():
    if m == wmax:
        wscan.append(i)

for h in hscan:
    for w in wscan:
        if not (h, w) in expl:
            print(hmax + wmax)
            exit()

print(hmax + wmax - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W, M = map(int, input().split())
row = [0] * (H + 1)
col = [0] * (W + 1)

hw = []
d = defaultdict(int)

for _ in range(M):
    h, w = map(int, input().split())
    d[(h, w)] = 1
    row[h] += 1
    col[w] += 1

r_max = 0
ri = []
c_max = 0
ci = []

for i, cnt in enumerate(col):
    if not cnt:
        continue
    if cnt > c_max:
        c_max = cnt
        ci = [i]
    elif cnt == c_max:
        ci.append(i)

for i, cnt in enumerate(row):
    if not cnt:
        continue
    if cnt > r_max:
        r_max = cnt
        ri = [i]
    elif cnt == r_max:
        ri.append(i)

ans = c_max + r_max


for r in ri:
    for c in ci:
        if not d[(r, c)]:
            print(ans)
            exit()

print(ans - 1)

Submission status: Accepted

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

H,W,M=map(int,input().split())
B=set([tuple(map(int,input().split())) for i in range(M)])

HH=[0]*(H+1)
WW=[0]*(W+1)

for x,y in B:
    HH[x]+=1
    WW[y]+=1

MAXH=max(HH)
MAXW=max(WW)

ANS=MAXH+MAXW-1

HLIST=[]
WLIST=[]
for i in range(1,H+1):
    if HH[i]==MAXH:
        HLIST.append(i)

for j in range(1,W+1):
    if WW[j]==MAXW:
        WLIST.append(j)

for i in HLIST:
    for j in WLIST:
        if (i,j) in B:
            continue
        else:
            print(ANS+1)
            sys.exit()
print(ANS)