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, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    h, w, m = i_map()
    num_list = i_row_list(m)

    if h == 1 or w == 1:
        print(m)
        exit()

    h_list = []
    w_list = []

    count = 0

    for num in num_list:
        h_list.append(num[0])
        w_list.append(num[1])

    co_h_list = Counter(h_list)
    co_w_list = Counter(w_list)

    # print(num_list)
    # print(co_h_list.most_common())
    # print(co_w_list.most_common())

    h_max_key = co_h_list.most_common()[0][0]
    h_max_value = co_h_list.most_common()[0][1]

    w_max_key = co_w_list.most_common()[0][0]
    w_max_value = co_w_list.most_common()[0][1]

    if h_max_value > w_max_value:
        max_index = h_max_key
        count = h_max_value

        tmp_list = []
        for num in num_list:
            if num[0] == max_index:
                continue
            tmp_list.append(num[1])

        if len(tmp_list) != 0:
            count += Counter(tmp_list).most_common()[0][1]
    elif h_max_value == w_max_value:
        max_index = h_max_key
        h_count = h_max_value

        tmp_list = []
        for num in num_list:
            if num[0] == max_index:
                continue
            tmp_list.append(num[1])

        if len(tmp_list) != 0:
            h_count += Counter(tmp_list).most_common()[0][1]     


        max_index = w_max_key
        w_count = w_max_value

        tmp_list = []
        for num in num_list:
            if num[1] == max_index:
                continue
            tmp_list.append(num[0])

        if len(tmp_list) != 0:  
            w_count += Counter(tmp_list).most_common()[0][1]

        count = max(h_count, w_count)
    else:
        max_index = w_max_key
        count = w_max_value

        tmp_list = []
        for num in num_list:
            if num[1] == max_index:
                continue
            tmp_list.append(num[0])

        if len(tmp_list) != 0:  
            count += Counter(tmp_list).most_common()[0][1]

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import collections
import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
items=[set() for _ in range(h+1)]
count_h=[0]*(h+1)
count_w=[0]*(w+1)
for _ in range(m):
    y,x=map(int,input().split())
    items[y].add(x)
    count_h[y]+=1
    count_w[x]+=1
count_num=collections.defaultdict(int)
for x in range(1,w+1):
    count_num[count_w[x]]+=1
count_cand=list(count_num.keys())
count_cand=sorted(count_cand,reverse=True)
ans=0
for y in range(1,h+1):
    value_y=count_h[y]
    count_tmp=collections.defaultdict(int)
    for x in items[y]:
        value_x=count_w[x]
        count_tmp[value_x]+=1
        ans=max(ans,value_y+value_x-1)
    for x in count_cand:
        if count_num[x]>count_tmp[x]:
            ans=max(ans,value_y+x)
            break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def main():
  input = stdin.readline
  H, W, M = map(int, input().split())
  B = set()
  Hc = {}
  Wc = {}
  for _ in range(M):
    h, w = map(int, input().split())
    B.add((h, w))
    if h not in Hc:
      Hc[h] = 0
    if w not in Wc:
      Wc[w] = 0
    Hc[h] += 1
    Wc[w] += 1
  Hm = max(Hc.values())
  Wm = max(Wc.values())
  Hp = [h for h, c in Hc.items() if c == Hm]
  Wp = [w for w, c in Wc.items() if c == Wm]
  #print(Hm, Wm, Hc, Wc)
  if len(B) < len(Hp) * len(Wp):
    print(Hm + Wm)
    exit()
  else:
    for h in Hp:
      for w in Wp:
        if (h, w) not in B:
          print(Hm + Wm)
          exit()
  #print('aaa')
  print(Hm + Wm - 1)
    
      
  
    
main()

Submission status: Accepted

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

objects = [list(map(int, input().split())) for _ in range(m)]

rows = [o[0]-1 for o in objects]
cols = [o[1]-1 for o in objects]
obj_dict = {(o[0]-1, o[1]-1): 1 for o in objects}

rows_appearance = [0] * h
for rr in rows:
    rows_appearance[rr] += 1

# print(rows_appearance)
m_row = max(rows_appearance)
m_row_num = 0
row_idx = []
for idx, rr in enumerate(rows_appearance):
    if rr == m_row:
        m_row_num += 1
        row_idx.append(idx)

cols_appearance = [0] * w
for cc in cols:
    cols_appearance[cc] += 1

# print(cols_appearance)
m_col = max(cols_appearance)
m_col_num = 0
col_idx = []
for idx, cc in enumerate(cols_appearance):
    if cc == m_col:
        m_col_num += 1
        col_idx.append(idx)


if m_row_num * m_col_num > m:
    # 鳩の巣原理。objectがないマスが必ずある。
    minus = 0
else:
    minus = 1
    for rr in row_idx:
        for cc in col_idx:
            if (rr, cc) not in obj_dict:
            # if rr, cc に対象物がなければ
                minus = 0
                break

print(m_col + m_row - minus)

Submission status: Accepted

Solution code:
import itertools

H,W,M=[int(i) for i in input().split(" ")]

target=[]
for i in range(M):
    target.append(tuple([int(j)-1 for j in input().split(" ")]))

target=set(target)

tate=[0 for i in range(H)]
yoko=[0 for i in range(W)]
for t in target:
    tate[t[0]]+=1
    yoko[t[1]]+=1



tate_max=max(tate)
yoko_max=max(yoko)

tate_max_ind=[]
for i,t in enumerate(tate):
    if t==tate_max:
        tate_max_ind.append(i)

yoko_max_ind=[]
for i,y in enumerate(yoko):
    if y==yoko_max:
        yoko_max_ind.append(i)

for iter in itertools.product(tate_max_ind,yoko_max_ind):
    if (iter in target)==False:
        print(tate_max+yoko_max)
        break

else:
    print(tate_max+yoko_max-1)

Submission status: Accepted

Solution code:
import heapq
# import collections
# from heapq import heapify
H, W, M = map(int, input().split())
hw = set([tuple(map(int, input().split())) for i in range(M)])
D1 = [0]*H
D2 = [0]*W

for x, y in hw:
    x -= 1
    y -= 1
    D1[x] += 1
    D2[y] += 1

X = max(D1)
Y = max(D2)

h = [x for x in range(H) if D1[x] == X]
w = [x for x in range(W) if D2[x] == Y]
ans = X+Y-1
for x in h:
    for y in w:
        if (x+1, y+1) not in hw:
            ans += 1
            print(ans)
            exit(0)
print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
#H, W, M = 300000, 300000, 300000
HL = [0 for _ in range(H)]
WL = [0 for _ in range(W)]
X = [list(map(int, input().split())) for i in range(M)]
#X = [[1, i+1] for i in range(M)]
for i in X:
  HL[i[0]-1] += 1
  WL[i[1]-1] += 1
HM, WM = max(HL), max(WL)
HF = [False for _ in range(H)]
WF = [False for _ in range(W)]
for i in range(H):
  if HL[i] == HM:
    HF[i] = True
for i in range(W):
  if WL[i] == WM:
    WF[i] = True
cnt = 0
for i in range(M):
  if HF[X[i][0]-1] * WF[X[i][1]-1]:
    cnt += 1
print(HM+WM-((sum(HF)*sum(WF))==cnt))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

h = []
w = []
c = set()
for i in range(M):
    a, b = map(int, input().split())
    h.append(a)
    w.append(b)
    c.add((a,b))

h = Counter(h)
w = Counter(w)

h = sorted(h.items(), key=lambda x:x[1], reverse=True)
w = sorted(w.items(), key=lambda x:x[1], reverse=True)

num_h = h[0][1]
num_w = w[0][1]

h_key = []
w_key = []

for i in range(len(h)):
    if h[i][1] == num_h:
        h_key.append(h[i][0])
    else:
        break

for i in range(len(w)):
    if w[i][1] == num_w:
        w_key.append(w[i][0])
    else:
        break

for hh in h_key:
    for ww in w_key:
        if (hh,ww) not in c:
            print(num_h + num_w)
            sys.exit()

print(num_h + num_w -1)

Submission status: Accepted

Solution code:
from math import gcd, sqrt, cos, radians, pi, factorial as f
from collections import defaultdict as d

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

dico = d(int)
for i in range(m):
	x, y = map(int, input().split())
	row[x-1] += 1
	col[y-1] += 1
	dico[str(x)+'-'+str(y)] = 1
	
m1 = max(row)
m2 = max(col)

res = m1 + m2
t1 = set()
for i in range(h):
	if row[i] == m1:
		t1.add(i)
		
t2 = set()
for i in range(w):
	if col[i] == m2:
		t2.add(i)		
total = len(t1) * len(t2)
counter = 0
for key in dico.keys():
	x, y = map(int, key.split('-'))
	if x-1 in t1 and y-1 in t2:counter+=1 

if total<=counter:res -=1

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
a,b,m=map(int,input().split())
r=defaultdict(int)
c=defaultdict(int)
d=defaultdict(int)
for i in range(m):
  x,y=map(int,input().split())
  d[(x,y)]=1
  r[x]+=1
  c[y]+=1
z=list()
zz=list()
x=max(r,key=r.get)
y=max(c,key=c.get)
for i in r.keys():
  if r[i]==r[x]:
    z.append(i)
for i in c.keys():
  if c[i]==c[y]:
    zz.append(i)
flag=False
for i in z:
  for j in zz:
    if d[(i,j)]==0:
      flag=True
      break
if flag==False:
  print(r[x]+c[y]-1)
else:
  print(r[x]+c[y])

Submission status: Accepted

Solution code:
def solve(B,H,W):
    tate = [0 for _ in range(H)]
    yoko = [0 for _ in range(W)]

    for b in B:
        tate[b[0]-1] += 1
        yoko[b[1]-1] += 1

    tate_max_kouho,yoko_max_kouho = set(),set()
    tate_max,yoko_max = 0,0
    for i in range(H):
        if tate_max == tate[i]:
            tate_max_kouho.add(i)
        elif tate_max < tate[i]:
            tate_max = tate[i]
            tate_max_kouho.clear()
            tate_max_kouho.add(i)

    for j in range(W):
        if yoko_max == yoko[j]:
            yoko_max_kouho.add(j)
        elif yoko_max < yoko[j]:
            yoko_max = yoko[j]
            yoko_max_kouho.clear()
            yoko_max_kouho.add(j)

    C = set() #置かれている爆破物のうち爆破地点候補にはいっている爆破物
    for b in B:
        if (b[0]-1) in tate_max_kouho and (b[1]-1) in yoko_max_kouho:
            C.add(b)

    if len(tate_max_kouho) * len(yoko_max_kouho) > len(C):
        return tate_max + yoko_max
    else:
        return tate_max + yoko_max - 1

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

    print(solve(B,H,W))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    H, W, M = read_values()
    T = [tuple(read_index()) for _ in range(M)]   

    HT = [0] * H
    WT = [0] * W
    for h, w in T:
        HT[h] += 1
        WT[w] += 1

    hm = max(HT)
    wm = max(WT)
    hs = set(h for h, v in enumerate(HT) if v == hm)
    ws = set(w for w, v in enumerate(WT) if v == wm)
    if len(hs) * len(ws) > M:
        print(hm + wm)
        return
    m = 0
    for h, w in T:    
        if h in hs and w in ws:
            m += 1

    print(hm + wm - (1 if len(hs) * len(ws) == m else 0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left


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

numbh = [0 for _ in range(h)]
numbw = [0 for _ in range(w)]

for b in bomb:
    bh, bw = b
    bh -= 1; bw -= 1
    numbh[bh] += 1
    numbw[bw] += 1

mbh, mbw = max(numbh), max(numbw)

mbh_i, mbw_i = [], []
for i in range(h):
    if mbh == numbh[i]:
        mbh_i.append(i)
for i in range(w):
    if mbw == numbw[i]:
        mbw_i.append(i)

cnt = 0
for b in bomb:
    bh, bw = b
    bh -= 1; bw -= 1
    p = bisect_left(mbh_i, bh)
    q = bisect_left(mbw_i, bw)
    if p < len(mbh_i) and mbh_i[p] == bh and q < len(mbw_i) and mbw_i[q] == bw:
        cnt += 1

ans = mbh+mbw
if cnt == len(mbh_i)*len(mbw_i):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    h, w, m = map(int, input().split())
    rows = defaultdict(int)
    cols = defaultdict(int)
    d1 = lambda :defaultdict(int)
    d2 = defaultdict(d1)
    m = map(int, read().split())
    ab = zip(m, m)
    for a, b in ab:
        rows[a-1] += 1
        cols[b-1] += 1
        d2[a-1][b-1] = 1
    rm = max(rows.values())
    cm = max(cols.values())
    rs = [i for i, v in rows.items() if v == rm]
    cs = [i for i, v in cols.items() if v == cm]
    r = rm + cm
    #p = set()
    for rse in rs:
        for cse in cs:
            if d2[rse][cse] == 0:
                print(r)
                sys.exit()
    print(r-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
g = defaultdict(int)
h,w,m = map(int, input().split())
d = [0]*(3*10**5+1)
e = [0]*(3*10**5+1)
for i in range(m):
  h,w = map(int, input().split())
  g[h*(3*10**5+1)+w]+=1
  d[h]+=1
  e[w]+=1
h1=max(d)
w1=max(e)
ans=h1+w1
h = []
l = []
for i in range(3*10**5+1):
  if d[i] == h1:
    h.append(i)
  if e[i] == w1:
    l.append(i)
for i in h:
  for j in l:
    if g[i*(3*10**5+1)+j]==0:
      print(ans)
      exit()
print(ans-1)

Submission status: Accepted

Solution code:
h,w,m=list(map(int,input().split()))
b=[]
r=[0]*(3*10**5+2)
c=[0]*(3*10**5+2)
for i in range(m):
    h,w=list(map(int,input().split()))
    r[h]=r[h]+1
    c[w]=c[w]+1
    b.append([h,w])
if max(r)>max(c):
    j=r.index(max(r))
    for i in range(len(b)):
        if b[i][0]==j:
            c[b[i][1]]=c[b[i][1]]-1
else:
    i=c.index(max(c))
    for j in range(len(b)):
        if b[j][1]==i:
            r[b[j][0]]=r[b[j][0]]-1
print(max(r)+max(c))

Submission status: Accepted

Solution code:
def main():
    h, w, m = list(map(int, input().split(" ")))
    x_hi = [0 for _ in range(h)]
    x_wi = [0 for _ in range(w)]

    bom_set = set([])
    for _ in range(m):
        hi, wi = list(map(int, input().split(" ")))
        hi-=1
        wi-=1
        x_hi[hi]+=1
        x_wi[wi]+=1
        bom_set.add((hi, wi))

    #obj_num_max_h = max(x_hi)
    #obj_num_max_w = max(x_wi)
    #print(obj_num_max_h, obj_num_max_w)
    #print(x_hi, x_wi)

    obj_num_max_h = 0
    ind_num_max_h = []
    for i, x in enumerate(x_hi):
        if obj_num_max_h<x:
            obj_num_max_h = x
            ind_num_max_h = [i]
        elif obj_num_max_h==x:
            ind_num_max_h.append(i)

    obj_num_max_w = 0
    ind_num_max_w = []
    for i, x in enumerate(x_wi):
        if obj_num_max_w<x:
            obj_num_max_w = x
            ind_num_max_w = [i]
        elif obj_num_max_w==x:
            ind_num_max_w.append(i)       

    for ih in ind_num_max_h:
        for iw in ind_num_max_w:
            if (ih, iw) in bom_set:
                continue
            else:
                print(obj_num_max_h + obj_num_max_w)
                exit()
    print(obj_num_max_h + obj_num_max_w - 1)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    H, W, M = MI()
    hh = [0]*(H+1)
    ww = [0]*(W+1)
    bomb = set()
    for _ in range(M):
        h, w = MI()
        hh[h] += 1
        ww[w] += 1
        bomb.add((h, w))
    h_max = max(hh)
    w_max = max(ww)
    ans = h_max+w_max
    h_index = [i for i, v in enumerate(hh) if v == h_max]
    w_index = [i for i, v in enumerate(ww) if v == w_max]
    flag = True
    for i in h_index:
        for j in w_index:
            if (i, j) not in bomb:
                flag = False
                break
        if not flag:
            break
    if flag:
        ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict

ii=jj=0
ia,ja=[],[]
rows=ddict(int)
cols=ddict(int)
H,W,M=map(int,input().split())
tgts=set()
for _ in range(M):
    i,j=map(int,input().split())
    tgts.add((i,j))

    rows[i]+=1
    cols[j]+=1
    x=rows[i]
    if x>ii:
        ii=x
        ia=[i]
    elif x==ii:
        ia.append(i)
    y=cols[j]
    if y>jj:
        jj=y
        ja=[j]
    elif y==jj:
        ja.append(j)



ans=0
for i in ia:
    for j in ja:
        k=rows[i]+cols[j]
        if (i,j) in tgts:
            k-=1
        else:
            ans=k
            break
        ans=max(ans,k)

print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
m+=1
n+=1
r=[0]*(n)
c=[0]*(m)
d={}
for _ in range(k):
  a,b=map(int,input().split())
  d[(a,b)]=1
  r[a]+=1
  c[b]+=1
m1=max(r)
x=[]
for i in range(n):
  if(r[i]==m1):
    x.append(i)
m2=max(c)
y=[]
for i in range(m):
  if(c[i]==m2):
    y.append(i)
ans=m1+m2
z=0
for i in x:
  for j in y:
    if((i,j) not in  d):
      z=-1
      break
if(z==0):
  print(ans-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

H,W,M = m()

data = []

setx = [0 for i in range(W)]
sety = [0 for i in range(H)]

for i in range(M):
    a,b = m()
    a -= 1
    b -= 1
    setx[b] += 1
    sety[a] += 1
    data.append([a,b])


mx = max(setx)
my = max(sety)
ans = 0
cox = 0
coy = 0
ans = my+mx
co = 0
for i in range(W):
    if setx[i] == mx:
        cox += 1
for i in range(H):
    if sety[i] == my:
        coy += 1
count = cox * coy
for po in data:
    if setx[po[1]]+sety[po[0]] == ans:
        co += 1
if co == count:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
Hcnt=[0]*H
Wcnt=[0]*W
hw=[]
hwset=set()
for i in range(M):
    h,w=map(lambda x:int(x)-1,input().split())
    hw.append((h,w))
    hwset.add((h,w))
    Hcnt[h]+=1
    Wcnt[w]+=1

mH=max(Hcnt)
mW=max(Wcnt)

max_H,max_W=set(),set()
for i in range(H):
    if Hcnt[i]==mH:
        max_H.add(i)
for i in range(W):
    if Wcnt[i]==mW:
        max_W.add(i)
        
if len(max_H)*len(max_W)>M:
    print(mH+mW)
    exit()

for i in max_H:
    for j in max_W:
        if not (i,j) in hwset:
            print(mH+mW)
            exit()
print(mH+mW-1)

Submission status: Accepted

Solution code:
# i行、j列それぞれにある爆弾の数を数える。
# 足して最大になるところにおけば良い。
H,W,M = map(int,input().split())
R = [0]*H
C = [0]*W
d = set()
ans = 0
for _ in range(M):
    h,w = map(int,input().split())
    h -= 1;w -= 1
    d.add((h,w))
    R[h] += 1
    C[w] += 1
r = []
c = []
tmp = 0
for i in range(H):
    if R[i] > tmp:
        tmp = R[i]
        r = [i]
    elif R[i] == tmp:
        r.append(i) 
    
ans += tmp
tmp = 0
for j in range(W):
    if C[j] > tmp:
        tmp = C[j]
        c = [j]
    elif C[j] == tmp:
        c.append(j)
ans += tmp
# もし選んだ行と列に共通して同じ爆弾が含まれていたら、それを削除したい。
select = []
for i in r:
    for j in c:
        if (i,j) in d:
            continue
        else:
            select = [i,j]
            break
if select == []:
    ans -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
b = []
x = [0 for _ in range(w)]
y = [0 for _ in range(h)]
for i in range(m):
  bh,bw = map(int,input().split())
  bh -= 1
  bw -= 1
  b.append((bh,bw))
  x[bw] += 1
  y[bh] += 1
#print(b,x,y)

mxx = max(x)
mxy = max(y)

cmxb = 0
for by,bx in b:
  if y[by]+x[bx] == mxx+mxy:
    cmxb += 1
cmxx = 0
for xi in x:
  if xi == mxx:
    cmxx += 1
cmxy = 0
for yi in y:
  if yi == mxy:
    cmxy += 1
#print(cmxb,cmxx,cmxy)

if cmxb == cmxx*cmxy:
  print(mxx+mxy-1)
else:
  print(mxx+mxy)

Submission status: Accepted

Solution code:
# E - Bomber
H,W,M = map(int,input().split())
bomb = set()
height = dict()
width = dict()
for i in range(M):
    h,w = map(int,input().split())
    bomb.add((h,w))
    if h in height:
        height[h] += 1
    else:
        height[h] = 1
    if w in width:
        width[w] += 1
    else:
        width[w] = 1
hei = dict()
wi = dict()
for h in height:
    if height[h] in hei:
        hei[height[h]].append(h)
    else:
        hei[height[h]] = [h]
for w in width:
    if width[w] in wi:
        wi[width[w]].append(w)
    else:
        wi[width[w]] = [w]
max_h = max(hei)
max_w = max(wi)
tmp = 1
for h in hei[max_h]:
    for w in wi[max_w]:
        if (h,w) not in bomb:
            tmp = 0
            break
print(max_h+max_w-tmp)

Submission status: Accepted

Solution code:
"""
max(row)+max(col)が実現可能かを検証する。
row2とcol2の組み合わせの中から、爆弾が存在しないような座標の組み合わせを見つけたい。
しかし、全組み合わせを見ていては、時間が足りない。
爆弾ベースで調べられないか？
各i行目に対して、j列目はダメ、というのが
"""

H,W,M = map(int,input().split())
row = [0]*(H)
col = [0]*(W)
memo = set()
bombMemoRow = {}
for _ in range(M):
    h,w = map(int,input().split())
    row[h-1] += 1
    col[w-1] += 1
    memo.add((h-1,w-1))
    if h-1 not in bombMemoRow:
        bombMemoRow[h-1] = []
    bombMemoRow[h-1].append(w-1)

rowMax = max(row)
colMax = max(col)
row2 = []
for i in range(H):
    if row[i] == rowMax:
        row2.append(i)

col2 = []
for i in range(W):
    if col[i] == colMax:
        col2.append(i)
col2Copy = col2[:]
col2 = set(col2)
col2Copy = set(col2Copy)

for r in row2:
    for c in bombMemoRow[r]:
        if c in col2:
            col2.remove(c)
    if len(col2) >= 1:
        print(rowMax+colMax)
        exit()
    for c in bombMemoRow[r]:
        if c in col2Copy:
            col2.add(c)
print(rowMax+colMax-1)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
H,W,M = map(int,input().split())
T = []
N_H = [0 for h in range(H)]
N_W = [0 for w in range(W)]
for _ in range(M):
	h,w = map(int,input().split())
	h -= 1
	w -= 1
	N_H[h] += 1
	N_W[w] += 1
	T.append((h,w))
nh = max(N_H)
h_candidate = [h for h in range(H) if N_H[h] == nh]
nw = max(N_W)
w_candidate = [w for w in range(W) if N_W[w] == nw]

combination = len(h_candidate) * len(w_candidate)
cnt = 0
for (h,w) in T:
	if N_H[h] == nh and N_W[w] == nw:
		cnt += 1
if cnt == combination:
	print(nh + nw - 1)
else:
	print(nh + nw)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, m = ns()

    hm = [0 for _ in range(h)]
    wm = [0 for _ in range(w)]

    m_pos = {}

    for _ in range(m):
        hi, wi = ns()
        hi, wi = hi - 1, wi - 1
        hm[hi] += 1
        wm[wi] += 1

        if hi in m_pos.keys():
            m_pos[hi].add(wi)
        else:
            m_pos[hi] = {wi}

    h_max = []
    w_max = []

    tmax = -1
    for i, hi in enumerate(hm):
        if hi > tmax:
            tmax = hi
            h_max = [i]
        elif hi == tmax:
            h_max.append(i)

    tmax = -1
    for i, wi in enumerate(wm):
        if wi > tmax:
            tmax = wi
            w_max = [i]
        elif wi == tmax:
            w_max.append(i)

    ans = 0
    breakflg = False

    for hi in h_max:
        for wi in w_max:
            if wi in m_pos[hi]:
                ans = max(ans, hm[hi] + wm[wi] - 1)
            else:
                ans = max(ans, hm[hi] + wm[wi])
                breakflg = True
                break
        if breakflg:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = [0 for _ in range(h)]
r = [0 for _ in range(w)]
bakuset = {}
for i, j in hw:
    # print(i, j)
    c[i-1] += 1
    r[j-1] += 1
    if not str(i-1) + "+" + str(j-1) in bakuset:
        bakuset[str(i-1) + "+" + str(j-1)] = 0
    # print(bakuset, i-1, j-1)
    bakuset[str(i-1) + "+" + str(j-1)] += 1

ans = max(c) + max(r)

mc = max(c)
mr = max(r)
cc = []
rr = []

for i in range(h):
    if c[i] == mc:
        cc.append(i)

for i in range(w):
    if r[i] == mr:
        rr.append(i)

flag = 10**10

for i in cc:
    for j in rr:
        if not str(i) + "+" + str(j) in bakuset:
            flag = 0
            break
        flag = min(flag, bakuset[str(i) + "+" + str(j)])
    if not flag:
        break

if flag:
    ans -= flag

print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(H, W, M, HW):
    row = [0] * (H)
    col = [0] * (W)
    for h, w in HW:
        h, w = h - 1, w - 1
        row[h] += 1
        col[w] += 1
    mh = max(row)
    mw = max(col)
    mhc = len([i for i, h in enumerate(row) if h == mh])
    mwc = len([i for i, w in enumerate(col) if w == mw])
    cnt = 0
    for h, w in HW:
        h, w = h - 1, w - 1
        if row[h] == mh and col[w] == mw:
            cnt += 1

    print(mh + mw - (1 if mhc * mwc <= cnt else 0))

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, M = map(int, input().split())
    HW = [tuple(map(int, input().split())) for _ in range(M)]
    main(H, W, M, HW)

Submission status: Accepted

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
##
for _ in range(1):
    r,c,m=cin()
    d=dd(set)
    ro=[0]*r
    co=[0]*c
    for i in range(m):
        x,y=cin()
        ro[x-1]+=1
        co[y-1]+=1
        d[x-1].add(y-1)

    ans=0
    mar=[];mac=[]
    mar1=max(ro);mac1=max(co);
    for i in range(r):
        if(ro[i]==mar1):
            mar+=[i]
    for i in range(c):
        if(co[i]==mac1):
            mac+=[i]
##    print(mar ,mac)
    t=-1
    ans=mar1+mac1
    for i in mar:
        for j in mac:
            if(j not in d[i]):
                t=0
                break
    print(ans+t)
    
    
    
    
    

                    
                
    

    

        


    
        

    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far