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 operator import itemgetter
import sys
input = sys.stdin.buffer.readline

class SegmentTree:
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    build(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def build(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)


h, w, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]


cnt_h = [0] * h
cnt_w = [0] * w
memo_i = {}
for i in range(h):
    memo_i[i] = []

for i, j in info:
    i -= 1
    j -= 1
    cnt_h[i] += 1
    cnt_w[j] += 1
    memo_i[i].append(j)


st = SegmentTree(w, max, 0)
st.build(cnt_w)


ans = 0
for i in range(h):
    for j in memo_i[i]:
        st.update(j, cnt_w[j] - 1)
    ans = max(st.get_val(0, w) + cnt_h[i], ans)
    for j in memo_i[i]:
        st.update(j, cnt_w[j])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

H,W,M = map(int,input().split())
bomb = [[0,0] for _ in range(M)]
bomb_d = defaultdict(int)

for i in range(M):
    bomb[i] = list(map(int,input().split()))
    bomb[i][0] -= 1
    bomb[i][1] -= 1
    bomb_d[tuple(bomb[i])] = 1


dh = [0]*H
dw = [0]*W

for i in range(M):
    dh[bomb[i][0]] += 1
    dw[bomb[i][1]] += 1

Maxh = max(dh)
Maxw = max(dw)

h_p = []
w_p = []

for i in range(H):
    if dh[i] == Maxh:
        h_p.append(i)
for i in range(W):
    if dw[i] == Maxw:
        w_p.append(i)

f = 0
for h in h_p:
    for w in w_p:
        if bomb_d[(h,w)] != 1:
            f = 1
            break
    else:
        continue
    break

if f == 0:
    print(Maxh+Maxw-1)
else:
    print(Maxh+Maxw)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1


H,W,M=map(int,input().split())
hw=[0]*M
mask=(1<<20)-1
H_bomb=[0]*H
W_bomb=[0]*W
for i in range(M):
    h,w=map(int1,input().split())
    H_bomb[h]+=1
    W_bomb[w]+=1
    hw[i]=(h<<20)+w
hw.sort(reverse=1)

MAX_W_bomb=[-INF,set()]

for i,x in enumerate(W_bomb):
    if x>MAX_W_bomb[0]:
        MAX_W_bomb[0]=x
        MAX_W_bomb[1]=set([i])
    elif x==MAX_W_bomb[0]:
        MAX_W_bomb[1].add(i)

ans=0
res=hw.pop()
next_y,next_x=res>>20,res&mask
for y in range(H):
    tmp=H_bomb[y]
    MAXcnt=0
    while next_y==y:
        if next_x in MAX_W_bomb[1]:
            MAXcnt+=1
        if hw:
            res=hw.pop()
            next_y,next_x=res>>20,res&mask
        else:
            next_y,next_x=-1,-1
    if MAXcnt==len(MAX_W_bomb[1]):
        tmp+=MAX_W_bomb[0]-1
    else:
        tmp+=MAX_W_bomb[0]
    ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, M, HW):
    g = defaultdict(dict)
    for h, w in HW:
        g[h][w] = 1
    h = Counter(h for h, w in HW)
    w = Counter(w for h, w in HW)
    h = list(h.items())
    h.sort(reverse=True, key=lambda x: x[1])
    w = list(w.items())
    w.sort(reverse=True, key=lambda x: x[1])

    ans = 0
    mh = h[0][1]
    mw = w[0][1]
    for k, v in h:
        if v != mh:
            break
        for kk, vv in w:
            if vv != mw:
                break
            if k in g and kk in g[k]:
                ans = max(ans, v + vv - 1)
            else:
                return v + vv

    return ans


def main():
    H, W, M = read_int_n()
    HW = [read_int_n() for _ in range(M)]
    print(slv(H, W, M, HW))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

h,w,m = map(int,input().split())
yoko = [0] * h
tate = [0] * w
S = set()
for _ in range(m):
  i,j = map(int,input().split())
  i-=1
  j-=1
  yoko[i] += 1
  tate[j] += 1
  S.add((i,j))
MY = max(yoko)
MT = max(tate)
max_yokos = []
max_tates = []
for i in range(h):
  if yoko[i] == MY:
    max_yokos.append(i)
for j in range(w):
  if tate[j] == MT:
    max_tates.append(j)
lmy = len(max_yokos)
lmt = len(max_tates)
for i in max_yokos:
  for j in max_tates:
    if not (i,j) in S:
      print(MY + MT)
      exit()
print(MY + MT - 1)


# print(tate)
# print(yoko)

Submission status: Accepted

Solution code:
# by the authority of GOD    author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase
from collections import Counter,defaultdict

def main():
    h,w,m = map(int,input().split())
    tar = [tuple(map(int,input().split())) for _ in range(m)]
    tar = set(tar)
    row,col = Counter(),Counter()
    for i in tar:
        row[i[0]] += 1
        col[i[1]] += 1
    row1,col1 = defaultdict(list),defaultdict(list)
    for i in row:
        row1[row[i]].append(i)
    for i in col:
        col1[col[i]].append(i)
    x = max(row1)
    y = max(col1)
    fl = 1
    for i in row1[x]:
        for j in col1[y]:
            if (i,j) not in tar:
                fl = 0
                break
    print(x+y-fl)

#Fast IO 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")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

H,W,M = LI()
h,w = LIR(M,2)

c = [0]*W
r = [0]*H

d = defaultdict(int)
for i in range(M):
    r[h[i]-1] += 1
    c[w[i]-1] += 1
    d[(h[i]-1,w[i]-1)] = 1

max_c = -1
c_index = []
max_r = -1
r_index = []

for i in range(H):
    if r[i] > max_r:
        max_r = r[i]
        r_index = [i]
    elif r[i] == max_r:
        r_index.append(i)
    else:
        continue

for i in range(W):
    if c[i] > max_c:
        max_c = c[i]
        c_index = [i]
    elif c[i] == max_c:
        c_index.append(i)
    else:
        continue

ans = max_c+max_r
flag = False
for i in r_index:
    for j in c_index:
        if d[(i,j)] == 0:
            flag = True
            break
    if flag:
        break

if not flag:
    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().rstrip().split(" "))
B = set()
Hc = [0 for i in range(H)]
Wc = [0 for i in range(W)]
Hl = []
Wl = []
for i in range(M):
    h,w = map(int,input().rstrip().split(" "))
    Hc[h-1] += 1
    Wc[w-1] += 1
    B.add((h-1) * W + w-1)
Hm = max(Hc)
Wm = max(Wc)
ans = 0
for i in range(H):
    if Hc[i] == Hm:
        Hl.append(i)
for i in range(W):
    if Wc[i] == Wm:
        Wl.append(i)
if len(Hl) * len(Wl) > M:
    ans = Hm + Wm
else:
    for h in Hl:
        for w in Wl:
            if not h * W + w in B:
                ans = Hm + Wm
                break
    if ans == 0:
        ans = Hm + Wm - 1
print(ans)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
a = [0 for _ in range(h)]
b = [0 for _ in range(w)]
raw = []
for _ in range(m):
  x,y = map(int,input().split())
  raw.append([x-1,y-1])
  a[x-1] += 1
  b[y-1] += 1
#print(a,b)
#print(max(a),max(b))
ma = max(a)
mb = max(b)
A = set()
B = set()
for i in range(h):
  if a[i] == ma:
    A.add(i)
for j in range(w):
  if b[j] == mb:
    B.add(j)
la = len(A)
lb = len(B)
#print(A,B)
#print(la,lb)
cnt = la * lb
#print(cnt)
for xy in raw:
  x,y = xy
  if x in A and y in B:
    cnt -= 1
#print(cnt)
if cnt:
  print(ma+mb)
else:
  print(ma+mb-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

h, w, m = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(m)]
dicHW = defaultdict(set)

for h, w in HW:
  dicHW[h].add(w)

hd = defaultdict(int)
wd = defaultdict(int)

for i, j in HW:
  hd[i] += 1
  wd[j] += 1

hd = list(hd.items())
wd = list(wd.items())

hd.sort(key=lambda x: -x[1])
wd.sort(key=lambda x: -x[1])

kouhoh = []
kouhow = []

for i, j in hd:
  if j < hd[0][1]:
    break
  else:
    kouhoh.append(i)

for i, j in wd:
  if j < wd[0][1]:
    break
  else:
    kouhow.append(i)

for i in kouhoh:
  for j in kouhow:
    if j not in dicHW[i]:
      ans = hd[0][1] + wd[0][1]
      print(ans)
      exit()

ans = hd[0][1] + wd[0][1] - 1  
print(ans)

Submission status: Accepted

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

LH = [0] * H
LW = [0] * W

R = {}
for i in range(M):
  h = hw[i][0] - 1
  w = hw[i][1] - 1
  LH[h] += 1
  LW[w] += 1
  if h in R:
    R[h][w] = 1
  else:
    R[h] = {}
    R[h][w] = 1

mah = max(LH)
maw = max(LW)
DH = []
DW = []

for i in range(H):
  if LH[i] == mah:
    DH.append(i)
for i in range(W):
  if LW[i] == maw:
    DW.append(i)

ans = mah + maw
for i in DH:
  if LH[i] != mah: continue
  for j in DW:
    if LW[j] != maw: continue
    if i not in R:
      break
    if j not in R[i]:
      break
  else:
    continue
  break
else:
  print(ans - 1)
  exit()

print(ans)

Submission status: Accepted

Solution code:
def main():

    H, W, M = map(int, input().split())
    A = set()
    row = dict()
    col = dict()

    for _ in range(M):
        h, w = map(int, input().split())
        A.add((h-1, w-1))
        row[h-1] = row.get(h-1, 0) + 1
        col[w-1] = col.get(w-1, 0) + 1

    max_row = max(row.values())
    max_col = max(col.values())
    cand_row = set([h for h in row if row[h] == max_row])
    cand_col = set([w for w in col if col[w] == max_col])

    # print(row)
    # print(col)
    # print(max_row, max_col)
    if len(cand_row) * len(cand_col) > M:
        return max_row + max_col
    else:
        for h in cand_row:
            for w in cand_col:
                if (h, w) not in A:
                    return max_row + max_col
        # print('here')
        return max_row + max_col - 1


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

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    h, w, m = mi()
    bombs = [tuple(mi_0()) for _ in range(m)]
    bombs_set = set(bombs)

    x_count = [0] * h
    y_count = [0] * w
    for x, y in bombs:
        x_count[x] += 1
        y_count[y] += 1
    
    hm = max(x_count)
    wm = max(y_count)
    hm_group = [i for i, elm in enumerate(x_count) if elm == hm]
    wm_group = [i for i, elm in enumerate(y_count) if elm == wm]
    
    def check_no_bomb():
        # hm とする x, wm とする w のうち好きな組み合わせで bomb がない座標を引き当てられるか？
        if len(hm_group) * len(wm_group) > m:
            # 直積のどれかしらは bomb ではない
            return True
        else:
            # 直積を調べられる
            for x in hm_group:
                for y in wm_group:
                    if (x, y) not in bombs_set:
                        return True
            return False    
    
    print(hm + wm if check_no_bomb() else hm + wm - 1)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

HL = [0]*H
WL = [0]*W
B = []

for _ in range(M):
  h, w = map(int, input().split())
  B.append((h, w))
  HL[h-1] += 1
  WL[w-1] += 1

HM = max(HL)
WM = max(WL)

H_ans = [0]*H
W_ans = [0]*W

for i in range(H):
  if HL[i] == HM:
    H_ans[i] += 1

for j in range(W):
  if WL[j] == WM:
    W_ans[j] += 1

if sum(H_ans)*sum(W_ans) > M:
  print(HM+WM)
else:
  cnt = 0
  for h, w in B:
    if H_ans[h-1] + W_ans[w-1] == 2:
      cnt += 1
  if sum(H_ans)*sum(W_ans) > cnt:
    print(HM+WM)
  else:
    print(HM+WM-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb = set()

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb.add(((_h - 1),(_w - 1)))

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

max_h = []
max_w = []

for i in range(h):
  if h_cnt[i] == h_max:
    max_h.append(i)

for j in range(w):
  if w_cnt[j] == w_max:
    max_w.append(j)

flag = True

for i in max_h:
  for j in max_w:
    if (i, j) not in bomb:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
bomb = [0] * M
H_list = [0] * H
W_list = [0] * W
for i in range(M):
  h, w = map(int, input().split()) 
  bomb[i] = [h - 1, w - 1]
  H_list[h - 1] += 1
  W_list[w - 1] += 1
  
#print(HW, H_list, W_list)  
H_max = max(H_list)
W_max = max(W_list)
H_count = H_list.count(H_max)
W_count = W_list.count(W_max)
HW_max = H_max + W_max

count = 0
for i, j in bomb:
  if H_list[i] + W_list[j] == HW_max:
    count += 1
    
if count == H_count * W_count:
  x = 1
else:
  x = 0
  
print(HW_max - x)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
R=[set([]) for _ in range(H+1)]
C=[set([]) for _ in range(W+1)]
R_n=[0]*(H+1)
C_n=[0]*(W+1)
b=[]

for i in range(M):
    y,x=map(int,input().split())
    b.append((x,y))
    R[y].add(x)
    C[x].add(y)
    R_n[y]+=1
    C_n[x]+=1

R_m=max(R_n)
R_i=[i for i, x in enumerate(R_n) if x == R_m]
C_m=max(C_n)
C_i=[i for i, x in enumerate(C_n) if x == C_m]

flag=0
for i in C_i:
    for j in R_i:
        if not i in R[j]:
            flag=1
            ans=R_m+C_m
            break
    if flag==1:
        break

if flag==0:
    ans=R_m+C_m-1

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
H, W, N = map(int, input().split())
ys = [0] * (H + 1)
xs = [0] * (W + 1)
a = []
base = 10 ** 6
for i in range(N):
  y, x = map(int, input().split())
  ys[y] += 1
  xs[x] += 1
  a.append((y, x))
sy = sorted(ys[1: ])
sx = sorted(xs[1: ])
#print(sy, sx)
def check(k):
  res = 0
  for y, x in a:
    res -= (ys[y] + xs[x]) == k
    res += (ys[y] + xs[x]) > k

  #print(res, k)
  for y in sy:
    i = bl(sx, k - y)
    res += W - i
    #print(W - i, y, k, res)
  return res > 0

ok = 0
ng = N + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Submission status: Accepted

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

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

    rows = [0] * H
    cols = [0] * W
    ps = set()
    for _ in range(M):
        r, c = (int(x) - 1 for x in input().split())
        rows[r] += 1
        cols[c] += 1
        ps.add((r, c))

    erows = sorted(enumerate(rows), key=itemgetter(1), reverse=True)
    ecols = sorted(enumerate(cols), key=itemgetter(1), reverse=True)

    ans = 0
    for r, cnt_r in erows:
        for c, cnt_c in ecols:
            s = cnt_r + cnt_c
            if ans >= s:
                break
            cond = (r, c) in ps
            ans = max(ans, s - int(cond))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import itertools

def solve(ah, aw, s: set):
    ahh, ahc = ah
    aww, awc = aw
    if (ahh, aww) in s:
        return ahc+awc-1
    else:
        return ahc + awc

def main():
    H, W, M = map(int, input().split())
    LH = []
    LM = []
    s = set()
    for _ in range(M):
        h, w = map(int, input().split())
        LH.append(h)
        LM.append(w)
        s.add((h,w))
    
    ch = Counter(LH)
    cm = Counter(LM)

    ahp = ch.most_common()
    awp = cm.most_common()
    th = ahp[0][1]
    tw = awp[0][1]
    #print("t=", th + tw)
    ah = []
    for x in ahp:
        if x[1] == th:
            ah.append(x)
        else:
            break
    aw = []
    for x in awp:
        if x[1] == tw:
            aw.append(x)
        else:
            break
    ans = solve(ah[0], aw[0], s)
    for x, y in itertools.product(ah, aw):
        z = solve(x, y, s)
        if z > ans:
            print(z)
            exit()
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
a=dict()
b=dict()
points=set()
for i in range (m):
    x,y=map(int,input().split())
    points.add((x,y))
    if x in a:
        a[x]+=1
    else:
        a[x]=1
    if y in b:
        b[y]+=1
    else:
        b[y]=1
m1=max(a.values())
m2=max(b.values())
s1=set()
s2=set()
for i in a:
    if a[i]==m1:
        s1.add(i)
for i in b:
    if b[i]==m2:
        s2.add(i)
r=set()
for i in points:
    if i[0] in s1 and i[1] in s2:
        r.add(i)
if len(r)==len(s1)*len(s2):
    print(m1+m2-1)
else:
    print(m1+m2)

Submission status: Accepted

Solution code:
from collections import defaultdict
h,w,m = [int(x) for x in input().split()]
hc = [0]*h
wc = [0]*w
d = defaultdict(int)
for i in range(m):
    hh,ww = [int(x) for x in input().split()]
    wc[ww-1] += 1
    hc[hh-1] += 1
    d[(hh-1)*3*(10**5)+ww-1] = 1
mhc = max(hc)
mwc = max(wc)
mhcIndex = [i for i, x in enumerate(hc) if x == mhc]
mwcIndex = [i for i, x in enumerate(wc) if x == mwc]
ans = mhc + mwc
for i in mhcIndex:
    for j in mwcIndex:
        if d[i*3*(10**5)+j] == 0:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
def examA():
    N, X, T = LI()
    ans = (1 + (N-1)//X)*T
    print(ans)
    return

def examB():
    N = SI()
    s = 0
    for n in N:
        s += int(n)
    if s%9==0:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    now = A[0]
    cnt = 0
    for i in range(N):
        if now>A[i]:
            cnt += now-A[i]
        if now<A[i]:
            now = A[i]
    ans = cnt
    print(ans)
    return

def examD():
    def bfs_grid(h, w, s, g, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue = deque()
            queue.append(s)
            cost = 0
            distance[s[0]][s[1]] = cost
            used = [s]
            while(True):
                while len(queue):
                    y, x = queue.popleft()
                    for i in range(4):
                        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '#'):
                            if distance[ny][nx] != inf:
                                continue
                            queue.append((ny, nx))
                            distance[ny][nx] = cost
                            used.append((ny,nx))

                #print(used)

                if distance[g[0]][g[1]]==inf:
                    cost += 1
                    used_ne = []
                    for y,x in used:
                        for i in range(5):
                            nx = x + [-2, -1, 0, 1, 2][i]
                            if not 0<=nx<W:
                                continue
                            for j in range(5):
                                ny = y + [-2, -1, 0, 1, 2][j]
                                if not 0<=ny<H:
                                    continue
                                if distance[ny][nx] != inf:
                                    continue
                                if maze[ny][nx]=="#":
                                    continue
                                queue.append((ny,nx))
                                distance[ny][nx] = cost
                                used_ne.append((ny,nx))
                    used = used_ne

                    if not queue:
                        #print(distance)
                        return -1
                    continue

                return cost


            return distance

        return bfsg()
    H, W = LI()
    C = LI()
    D = LI()
    C[0] -= 1; C[1] -= 1
    D[0] -= 1; D[1] -= 1
    S = [SI()for _ in range(H)]
    ans = bfs_grid(H, W, C, D, S)
    print(ans)
    return

def examE():
    H, W, M = LI()
    S = set()
    SH = [[0,i]for i in range(W)]
    SW = [[0,i]for i in range(H)]
    for _ in range(M):
        h, w = LI()
        h -= 1; w -= 1
        S.add((h,w))
        SW[h][0] += 1
        SH[w][0] += 1
    #print(S)
    SH.sort(reverse=True)
    SW.sort(reverse=True)
    #print(SH)
    #print(SW)
    max_SH = SH[0][0]
    max_SW = SW[0][0]
    for h in range(H):
        if SW[h][0]!=max_SW:
            break
        h1 = SW[h][1]
        for w in range(W):
            if SH[w][0] != max_SH:
                break
            w1 = SH[w][1]
            if (h1,w1) not in S:
                #print(h1,w1)
                ans = max_SH+max_SW
                print(ans)
                return

    ans = max_SH+max_SW-1
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
h,w,m = map(int, input().split())
hw = [list(map(int, input().split())) for i in range(m)]
x = [0]*h
y = [0]*w
used = set()
for hh,ww in hw:
    hh -= 1
    ww -= 1
    x[hh] += 1
    y[ww] += 1
    used.add((hh,ww))

x_max = max(x)
y_max = max(y)
x_pos = [i for i in range(h) if x[i] == x_max]
y_pos = [i for i in range(w) if y[i] == y_max]

ans = x_max+y_max-1
end = False
for x in x_pos:
    for y in y_pos:
        if (x,y) in used:
            continue
        else:
            ans += 1
            end = True
            break
    if end:
        break
print(ans)