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, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


h, w, m = inpl()
dic1 = [0] * h
dic2 = [0] * w
mine = [set() for i in range(h)]
for _ in range(m):
    y, x = inpl()
    dic1[y - 1] += 1
    dic2[x - 1] += 1
    mine[y - 1].add(x - 1)

sub1 = []
tmp = -1
for i in range(h):
    if tmp < dic1[i]:
        sub1 = [i]
        tmp = dic1[i]
    elif tmp == dic1[i]:
        sub1.append(i)
temp = -1
sub2 = []
for i in range(w):
    if temp < dic2[i]:
        sub2 = [i]
        temp = dic2[i]
    elif temp == dic2[i]:
        sub2.append(i)
ans = -1
FLAG = False
for i in sub1:
    for j in sub2:
        if j not in mine[i]:
            ans = 0
            FLAG = True
            break
    if FLAG:
        break
print(ans + tmp + temp)

Submission status: Accepted

Solution code:
import numpy as np
h, w, m = map(int, input().split())

hcnt = [0] * w
wcnt = [0] * h
field = {}
for i in range(m):
    y, x = map(int, input().split())
    y -= 1; x -= 1
    wcnt[y] += 1
    hcnt[x] += 1
    row = field.get(y, {})
    row[x] = True
    field[y] = row
def f(y, x):
    return bool(field.get(y, {}).get(x))
# print(wcnt)
# print(hcnt)
hmax = max(hcnt)
wmax = max(wcnt)
ans = hmax + wmax - 1
harg = np.argsort(hcnt)[::-1]
warg = np.argsort(wcnt)[::-1]
for i in harg:
    if hcnt[i] != hmax:
        break
    for j in warg:
        if wcnt[j] != wmax:
            break
        if not f(j, i):
            print(ans + 1)
            __import__("sys").exit()
print(ans)

Submission status: Accepted

Solution code:
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    row_n = [0 for _ in range(h)]
    col_n = [0 for _ in range(w)]
    for t in targets:
        row_n[t[0] - 1] += 1
        col_n[t[1] - 1] += 1
    max_r = max(row_n)
    max_c = max(col_n)
    mrow = [i for i in range(h) if row_n[i] == max_r]
    mcol = [i for i in range(w) if col_n[i] == max_c]
    for i in mrow:
        for j in mcol:
            if not i * h + j in tgs:
                print(max_r + max_c)
                exit()
    print max_r + max_c - 1
    return





h, w, m = RA()
targets = [RA() for _ in range(m)]
tgs = [(i[0]-1) * h + (i[1]-1) for i in targets]
tgs = set(tgs)
solve()

Submission status: Accepted

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

import heapq  # heapqライブラリのimport
Hs = [0]*(H+1)
Ws = [0]*(W+1)
HW = {}
for i in range(M):
    X,Y = B[i][0],B[i][1]
    Hs[X]+=1
    Ws[Y]+=1
    HW[str(X)+"_"+str(Y)] = 1

HM = max(Hs)
HMs = []
WM = max(Ws)
WMs = []
for i in range(H+1):
    if Hs[i]==HM:
        HMs.append(i)
for i in range(W+1):
    if Ws[i]==WM:
        WMs.append(i)
NHMs = len(HMs)
NWMs = len(WMs)

if NHMs*NWMs>M:
    print(HM+WM)
else:
    out = 0
    for i in range(NHMs):
        for j in range(NWMs):
            X,Y = HMs[i],WMs[j]
            if HW.get(str(X)+"_"+str(Y))!=1:
                out = 1
            else:
                continue
    print(out+HM+WM-1)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

H,W,M,*hw = map(int,open(0).read().split())

h = hw[::2]
w = hw[1::2]

hw_set = set((hi,wi) for hi,wi in zip(h,w))


raw_count = Counter(h).most_common()
col_count = Counter(w).most_common()


raw_max = raw_count[0][1]
col_max = col_count[0][1]

ans = 0
for hi, rcount in raw_count:
    if rcount<raw_max:break
    for wi, ccount in col_count:
        if ccount<col_max: break
        
        if (hi,wi) in hw_set:
            ans = raw_max + col_max - 1
        else:
            print(raw_max + col_max)
            sys.exit()

print(ans)

Submission status: Accepted

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

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

count_H = [0 for _ in range(H)]
count_W = [0 for _ in range(W)]
bomb = set()

for _ in range(M):
  h,w = map(int, input().split())
  bomb.add((h-1,w-1))
  count_H[h-1] += 1
  count_W[w-1] += 1

def argmax(L):
  indices = []
  maximum = -1
  for i in range(len(L)):
    if L[i] > maximum:
      indices = [i]
      maximum = L[i]
    elif L[i] == maximum:
      indices.append(i)
  return indices,maximum

indices_H,max_H = argmax(count_H)
indices_W,max_W = argmax(count_W)

answer = max_H + max_W - 1
flg = -1
for h in indices_H:
  for w in indices_W:
    if (h,w) not in bomb:
      answer = max_H + max_W
      flg = 0
      break
  if flg == 0:
    break

print(answer)

Submission status: Accepted

Solution code:
from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
dic = {}
mwi=deque([])
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]
 
for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = {}
    dic[a][b]=1
  else:
    dic[a][b]=1
 
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
 
  #ans[a][b]+=1

for i in mhi:
  for j in mwi:
    if not j in dic[i]:
      print(mw+mh)
      quit()

print(mh+mw-1)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

h, w, m = map(int, input().split())
l = 3 * pow(10, 5) + 5
cnt1, cnt2 = [[0, i] for i in range(l)], [[0, i] for i in range(l)]
d = {}
for _ in range(m):
    x, y = map(int, input().split())
    i = x + y * 1000000
    d[i] = 1
    cnt1[x][0] += 1
    cnt2[y][0] += 1
cnt1.sort(reverse = True)
cnt2.sort(reverse = True)
ans = cnt1[0][0] + cnt2[0][0] - 1
for i in range(l):
    if not cnt1[i][0] == cnt1[0][0]:
        break
    for j in range(l):
        if not cnt2[j][0] == cnt2[0][0]:
            break
        if not ((cnt1[i][1]) + (cnt2[j][1]) * 1000000) in d:
            print(ans + 1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
import random
import time
start=time.time()
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
hh.sort(reverse=1)
t=hh[0][0]
hhh=[]
for x,i in hh:
  if x==t:hhh.append((x,i))
ans=[]
random.shuffle(w)
for j in w:
  for x,i in hhh:
    if (i,j) in hw:
      ans.append(s+x-1)
    else:
      exit(print(s+x))
  if time.time()-start>=1.7:
    m=ans[0]
    if h-1000<=len(hhh)<=h-random.randint(10,1000):m+=1
    exit(print(m))
print(ans[0])

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, M, BOMs):
    h_count = [[0, i] for i in range(H + 1)]
    w_count = [[0, i] for i in range(W + 1)]
    bom_map_h = [[] for i in range(H + 1)]
    BOMs.sort(key=lambda x: x[1])
    for bom in BOMs:
        h_count[bom[0]][0] += 1
        w_count[bom[1]][0] += 1
        bom_map_h[bom[0]].append(bom[1])
    h_count.sort(reverse=True)
    w_count.sort(reverse=True)
    h_max = h_count[0][0]
    w_max = w_count[0][0]
    ans = h_max + w_max - 1
    flg = False
    for hc in h_count:
        if hc[0] < h_max:
            break
        for wc in w_count:
            if wc[0] < w_max:
                break
            aaa = bom_map_h[hc[1]]
            bbb = bisect.bisect_left(bom_map_h[hc[1]], wc[1])
            if len(aaa) == bbb or aaa[bbb] != wc[1]:
            # if bom_map_h[hc[1]][bisect.bisect_left(bom_map_h[hc[1]], wc[1])] != wc[1]:
            # if not wc[1] in bom_map_h[hc[1]]:
                ans = h_max + w_max
                flg = True
                break
        if flg:
            break
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    H, W, M = map(int, input().split())
    BOMs = [[int(i) for i in input().split()] for _ in range(M)]
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]

    # import random
    # H, W = 10, 10
    # M = random.randint(1, H * W)
    # BOMs = []
    # bom_map = [[0] * W for _ in range(H)]
    # i = 0
    # while i < M:
    #     h = random.randint(1, H)
    #     w = random.randint(1, W)
    #     if bom_map[h - 1][w - 1] == 0:
    #         i += 1
    #         bom_map[h-1][w-1]=1
    #         BOMs.append([h, w])
    # print(H, W, M)
    # import pprint
    # pprint.pprint(BOMs)

    # H, W, M = 10,10,7
    # BOMs = [[2, 2], [2, 3], [1, 6], [4, 6], [7, 3], [10, 6], [5, 5]]
    solve(H, W, M, BOMs)

Submission status: Accepted

Solution code:
H,W,d=map(int, input().split())
A={}
B={}
M={}
for i in range(d):
  a,b=map(int, input().split())
  if a not in A:
    A[a]=1
  else:
    A[a]+=1
  if b not in B:
    B[b]=1
  else:
    B[b]+=1
  if (a,b) not in M:
    M[(a,b)]=1
  else:
    M[(a,b)]+=1
AA=sorted(A.items(), key=lambda x:x[1],reverse=True)
BB=sorted(B.items(), key=lambda x:x[1],reverse=True)
AAA,BBB=[],[]
maa=AA[0][1]
for x,y in AA:
  if maa>y:
    break
  else:
    AAA.append((x,y))
mab=BB[0][1]
for x,y in BB:
  if mab>y:
    break
  else:
    BBB.append((x,y))
ans=AAA[0][1]+BBB[0][1]
for a,cnta in AAA:
  for b,cntv in BBB:
    if (a,b) not in M:
      print(ans)
      exit()
print(ans-1)

Submission status: Accepted

Solution code:
import random
import time
start=time.time()
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
hh.sort(reverse=1)
t=hh[0][0]
hhh=[]
for x,i in hh:
  if x==t:hhh.append((x,i))
ans=[]
random.shuffle(w)
for j in w:
  for x,i in hhh:
    if (i,j) in hw:
      ans.append(s+x-1)
    else:
      exit(print(s+x))
  if time.time()-start>=1.7:
    m=ans[0]
    if h-100000<=len(hhh)<=h-random.randint(100,1000):m+=1
    exit(print(m))
print(ans[0])

Submission status: Accepted

Solution code:
import random
import time
start=time.time()
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
hh.sort(reverse=1)
t=hh[0][0]
hhh=[]
for x,i in hh:
  if x==t:hhh.append((x,i))
ans=[]
random.shuffle(w)
for j in w:
  for x,i in hhh:
    if (i,j) in hw:
      ans.append(s+x-1)
    else:
      exit(print(s+x))
  if time.time()-start>=1.7:
    m=ans[0]
    if h-50000<=len(hhh)<=h-random.randint(10,100):m+=1
    exit(print(m))
print(ans[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H, W, M = list(map(int, input().split()))
    h = np.zeros(M, dtype=int)
    w = np.zeros(M, dtype=int)

    sum_h = np.zeros(H, dtype=int)
    sum_w = np.zeros(W, dtype=int)



    for m in range(M):
        tmp = list(map(int, input().split()))
        tmp_h = tmp[0]-1
        tmp_w = tmp[1]-1

        h[m] = tmp_h
        w[m] = tmp_w

        sum_h[tmp_h] += 1
        sum_w[tmp_w] += 1

    if H == 1:
        print(sum_w.sum())
        return
    elif W == 1:
        print(sum_h.sum())
        return

    ans1 = 0

    ans_h = np.argmax(sum_h) # hについては決定
    ans1 += max(sum_h)

    sum_w_copy = sum_w.copy()
    for m in range(M):
        if h[m] == ans_h:
            sum_w_copy[w[m]] -= 1

    ans_w = np.argmax(sum_w_copy)
    ans1 += max(sum_w_copy)

    ans2 = 0

    ans_w = np.argmax(sum_w)
    ans2 += max(sum_w)

    sum_h_copy = sum_h.copy()
    for m in range(M):
        if w[m] == ans_w:
            sum_h_copy[h[m]] -= 1

    ans_h = np.argmax(sum_h_copy)
    ans2 += max(sum_h_copy)

    print(max(ans1, ans2))
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
h_lis=[0]*H
w_lis=[0]*W
hw_set=set()

for _ in range(M):
    h,w=map(int,input().split())
    h_lis[h-1]+=1
    w_lis[w-1]+=1
    hw_set.add((h-1,w-1))
    
h_max=max(h_lis)
w_max=max(w_lis)

h_maxlis=[i for i, x in enumerate(h_lis) if x==h_max]
w_maxlis=[i for i, x in enumerate(w_lis) if x==w_max]
import sys

for hi in h_maxlis:
    for wi in w_maxlis:
        if (hi,wi) not in hw_set:
            print(h_max+w_max)
            sys.exit()
else:
    print(h_max+w_max-1)

Submission status: Accepted

Solution code:
import random
import time
start=time.time()
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
hh.sort(reverse=1)
t=hh[0][0]
hhh=[]
for x,i in hh:
  if x==t:hhh.append((x,i))
ans=[]
random.shuffle(w)
for j in w:
  for x,i in hhh:
    if (i,j) in hw:
      ans.append(s+x-1)
    else:
      exit(print(s+x))
  if time.time()-start>=1.7:
    m=ans[0]
    if h-50000<=len(hhh)<=h-random.randint(1,30):m+=1
    exit(print(m))
print(ans[0])

Submission status: Accepted

Solution code:
h,w,m=(int(i) for i in input().split())
l1=[]
l2=[0]*h
l3=[0]*w
for i in range(m):
    x,y=(int(i) for i in input().split())
    l1.append((x,y))
    l2[x-1]+=1
    l3[y-1]+=1
m1=max(l2)
m2=max(l3)
m3=max(m1,m2)
if(m1>m2):
    l4=[0]*w
    k=l2.index(m1)
    for i in range(m):
        if(l1[i][0]!=k+1):
           l4[l1[i][1]-1]+=1
    k1=max(l4)
    print(m3+k1)
else:
    l4=[0]*h
    k=l3.index(m2)
    for i in range(m):
        if(l1[i][1]!=k+1):
           l4[l1[i][0]-1]+=1
    k1=max(l4)
    print(m3+k1)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
H, W, M = [int(x) for x in input().split()]

ty = [0] * M
tx = [0] * M
target = defaultdict(bool)  # int/bool/list....
for i in range(M):
    ty[i], tx[i] = [int(x) for x in input().split()]
    target[(ty[i], tx[i])] = True

cntY = Counter(ty)
cntY = sorted(cntY.items(), key = lambda x:x[1], reverse = True)
ys = []
max_in_row = cntY[0][1]  # 出現回数max
for y, times in cntY:
    if times == max_in_row:
        ys.append(y)

cntX = Counter(tx)
cntX = sorted(cntX.items(), key = lambda x:x[1], reverse = True)
xs = []
max_in_col = cntX[0][1]  # 出現回数max
for x, times in cntX:
    if times == max_in_col:
        xs.append(x)

ans = max_in_row + max_in_col - 1
for y in ys:
    for x in xs:
        if target[(y, x)] == False:
            ans = max_in_row + max_in_col
            break

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid):  # fix inputs here
    console("----- solving ------")

    target_set = set([tuple(xy) for xy in grid])

    c1 = Counter([x for x,y in grid])
    c2 = Counter([y for x,y in grid])

    cx = sorted(c1.items(), key=lambda x:x[1])[::-1]
    cy = sorted(c2.items(), key=lambda x:x[1])[::-1]

    max_c1 = max(c1.values())
    max_c2 = max(c2.values())

    cxk = [k for k,v in cx if v == max_c1]
    cyk = [k for k,v in cy if v == max_c2]

    if max_c1 == 1:
        return min(len(grid), 1+max(c2.values()))
    if max_c2 == 1:
        return min(len(grid), 1+max(c1.values()))

    console(max(c1), max(c2))
    console(cx)
    console(cy)
    console(cxk)
    console(cyk)
    console(target_set)

    for x in cxk:
        for y in cyk:
            if (x,y) not in target_set:
                console(x,y)
                return max_c1 + max_c2
    return max_c1 + max_c2 - 1


def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _,_,nrows = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(map(int,input().split())))

    res = solve(grid)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

Solution code:
def main():
    h, w, m = map(int, input().split())
    A = [0] * h
    B = [0] * w
    Bomb = set()
    for _ in range(m):
        hi, wi = map(lambda x: int(x) - 1, input().split())
        A[hi] += 1
        B[wi] += 1
        Bomb.add((hi, wi))
    ma, mb = max(A), max(B)
    A = [i for i, a in enumerate(A) if a == ma]
    B = [i for i, b in enumerate(B)if b == mb]
    if len(A) * len(B) > m:
        print(ma + mb)
    else:
        f = False
        for i in A:
            for j in B:
                if (i, j) not in Bomb:
                    f = True
                    break
        print(ma + mb) if f else print(ma + mb - 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


# def valid(a, b):
#     return 0 <= a < n and 0 <= b < m
#
#
# n, m = sp()
# sx, sy = sp()
# ex, ey = sp()
# sx -= 1
# sy -= 1
# ex -= 1
# ey -= 1
# mat = [list(data()) for i in range(n)]
# answer = 10 ** 10
# q = deque()
# q.append([sx, sy, 0])
# x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
# vis = [[0] * m for _ in range(n)]
# vis[sx][sy] = 1
# while q:
#     sx, sy, jm = q.popleft()
#     if sx == ex and sy == ey:
#         answer = min(answer, jm)
#         continue
#     cnt = 0
#     for i in range(4):
#         tx, ty = sx + x[i], sy + y[i]
#         if valid(tx, ty) and mat[tx][ty] == ".":
#             if tx == ex and ty == ey:
#                 answer = min(answer, jm)
#                 cnt += 1
#             elif not vis[tx][ty]:
#                 q.append([tx, ty, jm])
#                 vis[tx][ty] = 1
#                 cnt += 1
#     if cnt == 0:
#         jm += 1
#         for i in range(-2, 3):
#             for j in range(-2, 3):
#                 tx, ty = sx + i, sy + j
#                 if valid(tx, ty) and mat[tx][ty] == ".":
#                     if tx == ex and ty == ey:
#                         answer = min(answer, jm)
#                     elif not vis[tx][ty]:
#                         q.append([tx, ty, jm])
#                         vis[tx][ty] = 1
# if answer == 10 ** 10:
#     print(-1)
#     exit()
# print(answer)
n, m, b = sp()
c1, c2 = [0] * n, [0] * m
s = set()
for i in range(b):
    x, y = sp()
    x -= 1
    y -= 1
    c1[x] += 1
    c2[y] += 1
    s.add((x, y))
answer = 0
m1, m2 = max(c1), max(c2)
l1, l2 = [], []
for i in range(n):
    if c1[i] == m1:
        l1.append(i)
for i in range(m):
    if c2[i] == m2:
        l2.append(i)
answer = m1 + m2 - 1
for i in l1:
    for j in l2:
        if (i, j) not in s:
            out(answer + 1)
            exit()
out(answer)

Submission status: Accepted

Solution code:
h, w, m = map(int,input().split())
dic_h = dict()
dic_w = dict()
max_h = [0, 0]
max_w = [0, 0]
c = dict()
for _ in range(m):
    x, y = map(int,input().split())
    c[(x, y)] = 1
    
    if dic_h.get(x):
        dic_h[x] += 1
        if dic_h[x] > max_h[0]:max_h = [dic_h[x], x]
        elif dic_h[x] == max_h[0]:max_h.append(x)
    else:
        dic_h[x] = 1
        if max_h[0] == 0:max_h = [1, x]
        elif max_h[0] == 1:max_h.append(x)
    
    if dic_w.get(y):
        dic_w[y] += 1
        if dic_w[y] > max_w[0]:max_w = [dic_w[y], y]
        elif dic_w[y] == max_w[0]:max_w.append(y)
    else:
        dic_w[y] = 1
        if max_w[0] == 0:max_w = [1, y]
        elif max_w[0] == 1:max_w.append(y)
        
res = max_h[0] + max_w[0] - 1
#print(max_h, max_w)
for i in range(len(max_h) - 1):
    for j in range(len(max_w) - 1):
        temp = (max_h[i + 1], max_w[j + 1])
        if c.get(temp):continue
        res += 1
        print(res)
        exit()
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H, W, M = list(map(int, input().split()))
    h = np.zeros(M, dtype=int)
    w = np.zeros(M, dtype=int)

    sum_h = np.zeros(H, dtype=int)
    sum_w = np.zeros(W, dtype=int)



    for m in range(M):
        tmp = list(map(int, input().split()))
        tmp_h = tmp[0]-1
        tmp_w = tmp[1]-1

        h[m] = tmp_h
        w[m] = tmp_w

        sum_h[tmp_h] += 1
        sum_w[tmp_w] += 1

    if H == 1:
        print(sum_w.sum())
        return
    elif W == 1:
        print(sum_h.sum())
        return

    ans1 = 0

    ans_h = np.argmax(sum_h) # hについては決定
    ans1 += max(sum_h)

    sum_w_dup = sum_w.copy()
    for m in range(M):
        if h[m] == ans_h:
            sum_w_dup[w[m]] -= 1

    ans_w = np.argmax(sum_w_dup)
    ans1 += max(sum_w_dup)

    ans2 = 0

    ans_w = np.argmax(sum_w)
    ans2 += max(sum_w)

    sum_h_dup = sum_h.copy()
    for m in range(M):
        if w[m] == ans_w:
            sum_h_dup[h[m]] -= 1

    ans_h = np.argmax(sum_h_dup)
    ans2 += max(sum_h_dup)

    print(max(ans1, ans2))
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
#from bisect import bisect_left, bisect_right
#from itertools import combinations, permutations, product
#from heapq import heappush, heappop
#from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W, M = rl()
B = set()
for i in range(M):
	h, w = rl()
	B.add((h-1, w-1))

ch = defaultdict(int)
cw = defaultdict(int)
for h, w in B:
	ch[h] += 1
	cw[w] += 1

mh = max(ch.values())
mw = max(cw.values())

his = []
for k, v in ch.items():
	if v != mh: continue
	his.append(k)

wis = []
for k, v in cw.items():
	if v != mw: continue
	wis.append(k)

ans = mh + mw
for i in his:
	for j in wis:
		if (i, j) not in B:
			print(ans)
			exit()
print(ans-1)

Submission status: Accepted

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

from collections import defaultdict
from collections import Counter
h_dic = defaultdict(int)#h[i]にいくつ爆発物があるか
w_dic = defaultdict(int)#w[i]にいくつ爆発物があるか

bomb = defaultdict(lambda:defaultdict(int))


for i in range(M):
  h,w = map(int,input().split())
  h_dic[h] += 1
  w_dic[w] += 1
  bomb[h][w] = 1
now_x = 0

firsth, num = max(h_dic.items(), key = lambda x:x[1])
for i,j in sorted(w_dic.items(), key = lambda x:x[1], reverse=True):
  if j <= now_x:
    break
  if bomb[firsth][i] == 1:
    x = j-1
  else:
    x = j
    now_x = x
    break
  now_x = x
fhans = num + now_x

now_x = 0
firstw, num = max(w_dic.items(), key = lambda x:x[1])
for i,j in sorted(h_dic.items(), key = lambda x:x[1], reverse=True):
  if j <= now_x:
    break
  if bomb[i][firstw] == 1:
    x = j-1
  else:
    x = j
    now_x = x
    break
  now_x = x
fwans = num + now_x
print(max(fhans,fwans))

Submission status: Accepted

Solution code:
import numpy as np
h, w, m = map(int, input().split())
H = [0 for _ in range(h)]
W = [0 for _ in range(w)]
ps = []
for _ in range(m):
  x, y = map(lambda p: int(p)-1, input().split())
  H[x] += 1
  W[y] += 1
  ps.append([x, y])
  
H = np.array(H)
W = np.array(W)
arrh = H == H.max()
arrw = W == W.max()
area = arrh.sum() * arrw.sum()
ans = int(H.max() + W.max())
for p in ps:
  if arrh[p[0]] and arrw[p[1]]:
    area -= 1
if area > 0:
  print(ans)
else:
  print(ans-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hb, wb = [0]*H, [0]*W
bomb = set()
for _ in range(M):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    hb[y] += 1
    wb[x] += 1
    bomb.add((y,x))

hindices = [*range(H)]
windices = [*range(W)]
sorted_hindices = sorted(hindices, key=lambda i: -hb[i])
sorted_hb = [hb[i] for i in sorted_hindices]
sorted_windices = sorted(windices, key=lambda i: -wb[i])
sorted_wb = [wb[i] for i in sorted_windices]

mh, mw = sorted_hb[0], sorted_wb[0]
for i in range(1, H):
    if sorted_hb[i] < mh:
        sorted_hb = sorted_hb[:i]
        sorted_hindices = sorted_hindices[:i]
        break
for i in range(1, W):
    if sorted_wb[i] < mw:
        sorted_wb = sorted_wb[:i]
        sorted_windices = sorted_windices[:i]
        break

for y in sorted_hindices:
    for x in sorted_windices:
        if (y,x) not in bomb:
            print(mh+mw)
            exit()

print(mh+mw-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    H, W, M = [int(x) for x in input().strip().split()]
    HM = [[i, 0] for i in range(H)]
    WM = [[i, 0] for i in range(W)]
    dic = defaultdict(int)
    for m in range(M):
        h, w = [int(x)-1 for x in input().strip().split()]
        dic[(h, w)] = 1
        HM[h][1] += 1
        WM[w][1] += 1
    HM.sort(reverse=True, key=lambda x: x[1])
    WM.sort(reverse=True, key=lambda x: x[1])
    # print(HM)
    # print(WM)
    maxh = HM[0][1]
    maxw = WM[0][1]
    ans = HM[0][1] + WM[0][1] - 1
    for h in range(H):
        if HM[h][1] != maxh:
            break
        for w in range(W):
            if WM[w][1] != maxw:
                break
            if dic[(HM[h][0], WM[w][0])] == 0:
                print(ans+1)
                return True
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

bombs = set()
for _ in range(m):
    hh, ww = map(lambda x: int(x)-1, input().split())
    H[hh] += 1
    W[ww] += 1
    bombs.add((hh, ww))

mh = max(H)
mw = max(W)
mhis = [i for i, x in enumerate(H) if x == mh]
mwis = [i for i, x in enumerate(W) if x == mw]

duplicated = True
for mhi in mhis:
    for mwi in mwis:
        if not (mhi, mwi) in bombs:
            duplicated = False
            break
            
ans = mh + mw - duplicated
print(ans)