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 collections import Counter

def main():
    h,w,m=map(int,input().split())
    hw=set([tuple(map(int,input().split())) for _ in range(m)])
    hs=Counter([i[0] for i in hw])
    ws=Counter([i[1] for i in hw])
    hh = [hs.most_common()[0]]
    for i in hs.items():
        if i[1] == hh[0][1]:
            hh.append(i)
    ww = [ws.most_common()[0]]
    for i in ws.items():
        if i[1] == ww[0][1]:
            ww.append(i)
    
    for i in hh:
        for j in ww:
            if (i[0], j[0]) not in hw:
                #print(hw, i[0],j[0])
                print(i[1] + j[1])
                return
    else:
        print(hh[0][1]+ww[0][1]-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    h_array = [ 0 for _ in range(h) ]
    w_array = [ 0 for _ in range(w) ]
    ps = set()
    for i in range(m):
        hi,wi = map( lambda x : int(x) - 1 , input().split() )
        h_array[hi] += 1
        w_array[wi] += 1
        ps.add( (hi,wi) )

    h_great = max(h_array)
    w_great = max(w_array)
    h_greats = list()
    w_greats = list()
    for i , hi in enumerate(h_array):
        if hi == h_great:
            h_greats.append(i)
    for i , wi in enumerate(w_array):
        if wi == w_great:
            w_greats.append(i)

    ans = h_great + w_great


    for _h in h_greats:
        for _w in w_greats:
            if (_h,_w) in ps:
                continue
            print(ans)
            exit()

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

h_array = [ 0 for i in range(h) ]
w_array = [ 0 for i in range(w) ]
ps = set()
for i in range(m):
    hi,wi = map( lambda x : int(x) - 1 , input().split() )
    h_array[hi] += 1
    w_array[wi] += 1
    ps.add( (hi,wi) )

h_great = max(h_array)
w_great = max(w_array)
h_greats = list()
w_greats = list()
for i , hi in enumerate(h_array):
    if hi == h_great:
        h_greats.append(i)
for i , wi in enumerate(w_array):
    if wi == w_great:
        w_greats.append(i)

ans = h_great + w_great


for _h in h_greats:
    for _w in w_greats:
        if (_h,_w) in ps:
            continue
        print(ans)
        exit()

print(ans-1)

Submission status: Accepted

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

h_array = [ 0 for i in range(h) ]
w_array = [ 0 for i in range(w) ]
ps = set()
for i in range(m):
    hi,wi = ( int(x)-1 for x in input().split() )
    h_array[hi] += 1
    w_array[wi] += 1
    ps.add( (hi,wi) )
h_great = max(h_array)
w_great = max(w_array)
h_greats = list()
w_greats = list()
for i , hi in enumerate(h_array):
    if hi == h_great:
        h_greats.append(i)
for i , wi in enumerate(w_array):
    if wi == w_great:
        w_greats.append(i)

ans = h_great + w_great


for _h in h_greats:
    for _w in w_greats:
        if (_h,_w) in ps:
            continue
        print(ans)
        exit()

print(ans-1)

Submission status: Accepted

Solution code:
import queue
h,w,m = ( int(x) for x in input().split() )

h_array = [ 0 for i in range(h) ]
w_array = [ 0 for i in range(w) ]
ps = set()
for i in range(m):
    hi,wi = ( int(x)-1 for x in input().split() )
    h_array[hi] += 1
    w_array[wi] += 1
    ps.add( (hi,wi) )
h_great = max(h_array)
w_great = max(w_array)
h_greats = list()
w_greats = list()
for i in range( h ):
    if h_array[i] == h_great:
        h_greats.append(i)
for i in range( w ):
    if w_array[i] == w_great:
        w_greats.append(i)

ans = h_great + w_great - 1

escaper = False

for i in range( len(h_greats) ):
    hi = h_greats[i]
    for j in range( len(w_greats) ):
        wi = w_greats[j]
        if (hi,wi) not in ps:
            ans += 1
            escaper = True
            break
    if escaper:
        break

print(ans)

Submission status: Accepted

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

cx=[0]*w
cy=[0]*h
xy=set()
for _ in range(m):
    y,x=map(int,input().split())
    x,y=x-1,y-1
    cx[x]+=1
    cy[y]+=1
    xy.add((x,y))

xmx=max(cx)
ymx=max(cy)
xs=[x for x in range(w) if cx[x]==xmx]
ys=[y for y in range(h) if cy[y]==ymx]

ans=xmx+ymx-1
ok=False
for y in ys:
    for x in xs:
        if (x,y) not in xy:
            ans+=1
            ok=True
            break
    if ok:
        break

print(ans)

Submission status: Accepted

Solution code:
H, W, m = map(int, input().split())
xs = [0] * H
ys = [0] * W
s = set()
for _ in range(m):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    xs[h] += 1
    ys[w] += 1
    s.add((h, w))

mx = max(xs)
my = max(ys)
mxs = set()
for i in range(H):
    if xs[i] == mx:
        mxs.add(i)
mys = set()
for i in range(W):
    if ys[i] == my:
        mys.add(i)
for x in mxs:
    for y in mys:
        if not (x, y) in s:
            print(mx + my)
            exit()
print(mx + my - 1)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    max_cnt_row = max(cnt_row)
    max_cnt_col = max(cnt_col)
    idx_row = []
    idx_col = []
    for i in range(h+1):
        if cnt_row[i] == max_cnt_row:
            idx_row.append(i)
    for j in range(w+1):
        if cnt_col[j] == max_cnt_col:
            idx_col.append(j)
    ans = max_cnt_row + max_cnt_col - 1
    for i in idx_row:
        for j in idx_col:
            if not (i, j) in bombs:
                ans = max_cnt_row + max_cnt_col
                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

xsct=[0]*w
ysct=[0]*h
ips=set()
for _ in range(m):
    y,x=map(int,input().split())
    x,y=x-1,y-1
    xsct[x]+=1
    ysct[y]+=1
    ips.add((x,y))

xsmx=max(xsct)
ysmx=max(ysct)

xs=[x for x in range(w) if xsct[x]==xsmx]
ys=[y for y in range(h) if ysct[y]==ysmx]

ans=xsmx+ysmx-1
ok=False
for y in ys:
    for x in xs:
        if (x,y) not in ips:
            ans+=1
            ok=True
            break
    if ok:
        break

print(ans)

Submission status: Accepted

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

xsct=[0]*w
ysct=[0]*h
ips=set()
xsmx=ysmx=0
for _ in range(m):
    y,x=map(int,input().split())
    x,y=x-1,y-1
    xsct[x]+=1
    ysct[y]+=1
    ips.add((x,y))
    xsmx=max(xsmx,xsct[x])
    ysmx=max(ysmx,ysct[y])

xs=[x for x in range(w) if xsct[x]==xsmx]
ys=[y for y in range(h) if ysct[y]==ysmx]

ans=xsmx+ysmx-1
ok=False
for y in ys:
    for x in xs:
        if (x,y) not in ips:
            ans+=1
            ok=True
            break
    if ok:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict

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

xs=[0]*w
ys=[0]*h
xsmx=ysmx=0
pts=set()
for _ in range(m):
    y,x=map(int,input().split())
    x,y=x-1,y-1
    xs[x]+=1
    ys[y]+=1
    pts.add((x,y))
    xsmx=max(xsmx,xs[x])
    ysmx=max(ysmx,ys[y])

xsc=[x for x in range(w) if xs[x]==xsmx]
ysc=[y for y in range(h) if ys[y]==ysmx]
ans=xsmx+ysmx-1
ok=False
for y in ysc:
    for x in xsc:
        if (x,y) not in pts:
            ans+=1
            ok=True
            break
    if ok:
        break

print(ans)

Submission status: Accepted

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

    h,w,m = map(int, input().split())
    h_count = [0 for _ in range(h)]
    w_count = [0 for _ in range(w)]
    pairs = set()

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

        h_count[hi] += 1
        w_count[wi] += 1

        pairs.add((hi,wi))

    h_max = max(h_count)
    w_max = max(w_count)
    hk = list()
    wk = list()

    for index , hj in enumerate(h_count):
        if hj == h_max:
            hk.append(index)
    
    for index, wj in enumerate(w_count):
        if wj == w_max:
            wk.append(index)

    ans = h_max + w_max

    for _h in hk:
        for _w in wk:
            hw = (_h, _w)

            if hw in pairs:
                continue

            print(ans)
            exit()
    print(ans -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

H, W, M = nn()
T = nm(M)

for i in range(M):
    T[i] = ldec(T[i])

dh = array1(H)
dw = array1(W)

dic = {}

for i in range(M):
    dh[T[i][0]] += 1
    dw[T[i][1]] += 1
    dic[(T[i][0], T[i][1])] = True

dhlist = []
dwlist = []

ansh = max(dh)
for i in range(len(dh)):
    if dh[i] == ansh:
        dhlist.append(i)

answ = max(dw)
for i in range(len(dw)):
    if dw[i] == answ:
        dwlist.append(i)

ans = ansh + answ

for i in dhlist:
    for j in dwlist:
        if (i, j) not in dic:
            print(ans)
            exit(0)

print(ans-1)

Submission status: Accepted

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

H_count = [0 for i in range(H)]
W_count = [0 for i in range(W)]

for i in range(M):
    h, w = map(lambda x:int(x) - 1, input().split())
    bombs.add((h, w))
    H_count[h] += 1
    W_count[w] += 1


A = max(H_count)
B = max(W_count)
Ah = []
Bw = []

for i, count in enumerate(H_count):
    if count == A:
        Ah.append(i)

for i, count in enumerate(W_count):
    if count == B:
        Bw.append(i)

ans = A + B
for h in Ah:
    for w in Bw:
        if (h, w) not in bombs:
            print(ans)
            exit()

print(ans - 1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=set()
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.add((th,tw))

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

for i in h_cand:
  for j in w_cand:
    if (i,j) not in l:
      print(h_max+w_max)
      exit()

print(h_max+w_max-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=set()
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.add((th,tw))

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

for i in h_cand:
  for j in w_cand:
    if (i,j) not in l:
      print(h_max+w_max)
      exit()

print(h_max+w_max-1)

Submission status: Accepted

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

hlist=[0]*H
wlist=[0]*W
hwset=set()
for _ in range(M):
  h,w=map(int,input().split())
  hlist[h-1]+=1
  wlist[w-1]+=1
  hwset.add((h-1,w-1))
  
hmax=max(hlist)
hlist2=[]
for i in range(H):
  if hlist[i]==hmax:
    hlist2.append(i)

wmax=max(wlist)
wlist2=[]
for i in range(W):
  if wlist[i]==wmax:
    wlist2.append(i)
#print(hlist2,wlist2)

H2=len(hlist2)
W2=len(wlist2)

if H2*W2>M:
  print(hmax+wmax)
else:
  for i in range(H2):
    ii=hlist2[i]
    for j in range(W2):
      jj=wlist2[j]
      if not (ii,jj) in hwset:
        print(hmax+wmax)
        sys.exit(0)
  else:
    print(hmax+wmax-1)

Submission status: Accepted

Solution code:
def calc():
  H,W,M = map(int, input().split())
  s = []
  hcount = [0]*H
  wcount = [0]*W
  for m in range(M):
    h,w = map(int, input().split())
    h = h - 1
    w = w - 1
    hcount[h] = hcount[h] + 1
    wcount[w] = wcount[w] + 1
    s.append((h,w))
  hmax = max(hcount)
  wmax = max(wcount)
  hmode = [h for h, x in enumerate(hcount) if x == hmax]
  wmode = [w for w, y in enumerate(wcount) if y == wmax]
  s = tuple(s)
  S = set(s)
  for h in hmode:
    for w in wmode:
      if ((h,w) not in S):
        return hmax + wmax
  return hmax + wmax - 1
  
if __name__ == '__main__':
    print(calc())

Submission status: Accepted

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    import sys
    input = sys.stdin.readline
    H,W,m=map(int,input().split())
    bomb=set()
    cnt1=[0 for i in range(H)]
    cnt2=[0 for i in range(W)]
    for i in range(m):
        h,w=map(int,input().split())
        bomb.add((h-1,w-1))
        cnt1[h-1]+=1
        cnt2[w-1]+=1
    m1=max(cnt1)
    m2=max(cnt2)
    hk,wk=[],[]
    for i,x in enumerate(cnt1):
        if x==m1:
           hk.append(i)
    for i,x in enumerate(cnt2):
        if x==m2:
           wk.append(i)
    ans=m1+m2
    for i in hk:
        for j in wk:
            if (i,j) in bomb:
                continue
            print(ans)
            exit()
    print(ans-1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    h, w, m = map(int, input().split())
    h_count = [0 for _ in range(h)]
    w_count = [0 for _ in range(w)]
    pairs = set()

    # KeyInsight:
    # x方向とy方向を独立に考える
    # 爆破できる数: x方向の最大値 + y方向の最大値
    #             x, y方向が交差する場合は-1
    for i in range(m):
        hi, wi = map(int, input().split())
        hi -= 1
        wi -= 1

        h_count[hi] += 1
        w_count[wi] += 1

        pairs.add((hi, wi))

    # 各方向の最大値を計算
    h_max = max(h_count)
    w_max = max(w_count)
    hk = list()
    wk = list()

    # 各方向で、最大値となる行もしくは列を抽出
    for index, hj in enumerate(h_count):
        if hj == h_max:
            hk.append(index)

    for index, wj in enumerate(w_count):
        if wj == w_max:
            wk.append(index)

    # 答えの候補
    ans = h_max + w_max

    # 範囲を限定して全探索
    # 合計が最大値となる組み合わせを全探索
    for _h in hk:
        for _w in wk:
            hw = (_h, _w)

            if hw in pairs:
                continue

            # 一つでも条件に合致したら、計算を打ち切る
            print(ans)
            exit()

    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

H, W, M = map(int, input().split())
h = [-1 for _ in range(M)]
w = [-1 for _ in range(M)]
s = set()
for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    s.add((h[i], w[i]))

# calc
hs = [0 for _ in range(H)]
ws = [0 for _ in range(W)]
for i in range(M):
    hs[h[i]] += 1
    ws[w[i]] += 1

#print('hs =', hs)
#print('ws =', ws)

hmax = max(hs)
wmax = max(ws)

ks = []
js = []

# 最大値の荷物がある場所を覚えておく
for k in range(H):
    if hmax == hs[k]:
        ks.append(k)
for j in range(W):
    if wmax == ws[j]:
        js.append(j)

ans = hmax + wmax

# クロスする場所に荷物があるかないかの確認
for k in range(len(ks)):
    for j in range(len(js)):
        if (ks[k], js[j]) not in s:
            print(ans)
            exit()
print(ans-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    h, w, m = map(int, input().split())
    h_count = [0 for _ in range(h)]
    w_count = [0 for _ in range(w)]
    pairs = set()

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

        h_count[hi] += 1
        w_count[wi] += 1

        pairs.add((hi, wi))

    h_max = max(h_count)
    w_max = max(w_count)
    hk = list()
    wk = list()

    for index, hj in enumerate(h_count):
        if hj == h_max:
            hk.append(index)

    for index, wj in enumerate(w_count):
        if wj == w_max:
            wk.append(index)

    ans = h_max + w_max

    for _h in hk:
        for _w in wk:
            hw = (_h, _w)

            if hw in pairs:
                continue

            print(ans)
            exit()

    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

h,w,m = readints()

r = [0]*h
c = [0]*w

d = [set() for i in range(h)]
for i in range(m):
    a,b = (x-1 for x in readints())
    r[a] += 1
    c[b] += 1
    d[a].add(b)

mr = max(r)
mc = max(c)
R = [i for i,x in enumerate(r) if x==mr]
C = [i for i,x in enumerate(c) if x==mc]

flag = 1
if len(R)*len(C)>m:
    flag = 0
else:
    for x in R:
        for y in C:
            if y not in d[x]:
                flag = 0
                break

print(max(r)+max(c)-flag)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import bisect
from operator import itemgetter

h,w,m = readints()

r = [0]*h
c = [0]*w

p = [readints() for i in range(m)]
p.sort(key=itemgetter(1))

d = [[] for i in range(h)]
for i in range(m):
    a,b = (x-1 for x in p[i])
    r[a] += 1
    c[b] += 1
    d[a].append(b)

mr = max(r)
mc = max(c)
R = [i for i,x in enumerate(r) if x==mr]
C = [i for i,x in enumerate(c) if x==mc]

flag = 1
if len(R)*len(C)>m:
    flag = 0
else:
    for x in R:
        for y in C:
            z = bisect.bisect_left(d[x],y)
            if z>=len(d[x]):
                flag = 0
                break
            else:
                if y != d[x][z]:
                    flag = 0
                    break

print(max(r)+max(c)-flag)

Submission status: Accepted

Solution code:
import bisect

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

rows, columns = [0]*H, [0]*W
for h, w in hw:
    rows[h-1] += 1
    columns[w-1] += 1
max_r, max_c = max(rows), max(columns)

argmax_r, argmax_c = [], []
for i in range(H):
    if max_r == rows[i]:
        argmax_r.append(i)

for i in range(W):
    if max_c == columns[i]:
        argmax_c.append(i)

for r in argmax_r:
    for c in argmax_c:
        idx = bisect.bisect_left(hw, [r+1, c+1])
        if idx == M or hw[idx] != [r+1,c+1]:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)

Submission status: Accepted

Solution code:
from collections import *
h, w, m = map(int, input().split())
mh = [0 for _ in range(h)]
mw = [0 for _ in range(w)]

z = []
for _ in range(m):
    x, y = map(int, input().split())
    z.append((x-1, y-1))
    mh[x-1] += 1
    mw[y-1] += 1

hc = Counter(mh)
wc= Counter(mw)
hm = max(mh)
wm= max(mw)

ans = hm + wm
tmp = 0
for x, y in z:
    if mh[x] + mw[y] == ans:
        tmp += 1

if tmp == hc[hm] * wc[wm]:
    print(ans - 1)
else:
    print(ans)

Submission status: Accepted

Solution code:
#-------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# ------------------- fast io --------------------

from math import gcd, ceil

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

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

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

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


h, w, m = map(int, input().split())
rs = [0] * h
cs = [0] * w

se = set()
for i in range(m):
    r, c =  map(int, input().split())
    rs[r - 1] += 1
    cs[c - 1] += 1
    se.add((r - 1) * w + c - 1)

rmax = max(rs)
cmax = max(cs)

remax = rs.count(rmax)
cemax = cs.count(cmax)
if remax * cemax > m:
    print(rmax + cmax)
    sys.exit(0)

rmaxs = [i for i, _ in enumerate(rs) if _ == rmax]
cmaxs = [i for i, _ in enumerate(cs) if _ == cmax]
for r in rmaxs:
    for c in cmaxs:
        if r * w + c not in se:
            print(rmax + cmax)
            sys.exit(0)

print(rmax + cmax - 1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0


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

col = [0]*W
row = [0]*H
elements = []
for i in range(M):
    h,w = map(int,readline().split())
    h,w = h-1,w-1
    elements.append((h,w))
    col[w] += 1
    row[h] += 1

def rank(lst,syoujun=False):
    res2 = list(set(lst))
    ans = []
    if syoujun:
        res2.sort()
    else:
        res2.sort(reverse=True)
    dic1 = dict()
    for i in range(len(res2)):
        dic1[res2[i]] = i
    for i in lst:
        #ans.append(dic1[i]) #zero-indexed
        ans.append(dic1[i] + 1) #one-indexed
    
    return ans

col2 = rank(col)
row2 = rank(row)

cmax = col2.count(1)
rmax = row2.count(1)

counter = 0
for i,j in elements:
    if col2[j] == 1 and row2[i] == 1:
        counter += 1

if counter == cmax*rmax:
    print(max(col) + max(row)-1)
else:
    print(max(col) + max(row))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
hh_dict = {}
ww_dict = {}
for hh in h_dict:
    if h_dict[hh] == h_max_count:
        hh_dict[hh] = h_max_count
for ww in w_dict:
    if w_dict[ww] == w_max_count:
        ww_dict[ww] = w_max_count
flag = 0
for hh in hh_dict:
    for ww in ww_dict:
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int, readline().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in 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 = [h for h, x in enumerate(X) if x == maxX]  
C = [w for w, y in enumerate(Y) if y == maxY] 

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)

Submission status: Accepted

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

row, col = [0] * H, [0] * W
for h, w in hw:
    row[h - 1] += 1
    col[w - 1] += 1

rowmax, colmax = max(row), max(col)
cnt = row.count(rowmax) * col.count(colmax)
for h, w in hw:
    if row[h - 1] == rowmax and col[w - 1] == colmax:
        cnt -= 1
print(rowmax + colmax - (cnt == 0))

Submission status: Accepted

Solution code:
import itertools

H,W,M=map(int,input().split())
d={}
nh=[0]*H
nw=[0]*W
for _ in range(M):
    h,w=map(int,input().split())
    h-=1
    w-=1
    d[(h,w)]=1
    nh[h]+=1
    nw[w]+=1
hmax=max(nh)
wmax=max(nw)
is_h=[i for i in range(H) if nh[i]==hmax]
is_w=[i for i in range(W) if nw[i]==wmax]

for i_h,i_w in itertools.product(is_h,is_w):
    if (i_h,i_w) not in d:
        print(hmax+wmax)
        break
else:
    print(hmax+wmax-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hw = set()
cnt_h, cnt_w = [0] * H, [0] * W
for i in range(M):
    x, y = map(int, input().split())
    hw.add((x - 1, y - 1))
    cnt_h[x - 1] += 1
    cnt_w[y - 1] += 1

max_h, max_w = max(cnt_h), max(cnt_w)

h_list = [h for h in range(H) if cnt_h[h] == max_h]
w_list = [w for w in range(W) if cnt_w[w] == max_w]

res = max_h + max_w - 1
for h in h_list:
    for w in w_list:
        if (h, w) not in hw:
            print(res + 1)
            exit()
print(res)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W,M=LI()
  h=[0]*H
  w=[0]*W
  d={}
  for _ in range(M):
    a,b=LI()
    a-=1
    b-=1
    h[a]+=1
    w[b]+=1
    d[(a,b)]=1

  h_koho=[]
  w_koho=[]

  h_max=max(h)
  w_max=max(w)

  for i,x in enumerate(h):
    if x==h_max:
      h_koho.append(i)
  for i,x in enumerate(w):
    if x==w_max:
      w_koho.append(i)

  for x in h_koho:
    for y in w_koho:
      if (x,y) not in d:
        return h_max+w_max

  return h_max+w_max-1

# main()
print(main())

Submission status: Accepted

Solution code:
import numpy as np
h,w,m=map(int, input().split())
hw=[tuple(map(int,input().split())) for i in range(m)]
H=np.zeros(h)
W=np.zeros(w)
for i in range(m):
    hi,wi=hw[i]
    H[hi-1]+=1
    W[wi-1]+=1
mh=max(H)
mw=max(W)
hmax=[i for i, x in enumerate(H) if x == mh]
wmax=[i for i, x in enumerate(W) if x == mw]
f=0
for i in range(m):
    hi,wi=hw[i]
    if H[hi-1]==mh and W[wi-1]==mw:
        f+=1
if len(hmax)*len(wmax)-f<1:
    print(int(mh+mw-1))
else:
    print(int(mh+mw))

Submission status: Accepted

Solution code:
def main():
    H,W,M = map(int,input().split())
    s = []
    h_cnt = [0 for i in range(H)]
    w_cnt = [0 for i in range(W)]
    for i in range(M):
        h,w = map(int,input().split())
        s.append([h-1,w-1])
        h_cnt[h-1] += 1
        w_cnt[w-1] += 1
    h_m,w_m = max(h_cnt), max(w_cnt)
    h_mp,w_mp = [],[]
    for i in range(H):
        if h_cnt[i] == h_m:
            h_mp.append(i)
    for i in range(W):
        if w_cnt[i] == w_m:
            w_mp.append(i)
    f = 0
    for i in range(M):
        if h_cnt[s[i][0]] == h_m and w_cnt[s[i][1]] == w_m:
            f += 1
    if len(w_mp)*len(h_mp)-f<1:
        print(h_m+w_m-1)
    else:
        print(h_m+w_m)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
s = []
r = [0] * (h + 1)
c = [0] * (w + 1)
for i in range(m):
    bh, bw = map(int, input().split())
    s.append([bh, bw])
    r[bh] += 1
    c[bw] += 1
R = max(r)
nr = {i for i, x in enumerate(r) if x == R}
C = max(c)
nc = {i for i, x in enumerate(c) if x == C}
count = sum(x in nr and y in nc for x, y in s)
print(R + C - (len(nr) * len(nc) == count))