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:
H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]
row = [0] * H
col = [0] * W
for i in range(M):
    row[hw[i][0] - 1] += 1
    col[hw[i][1] - 1] += 1
row_ = sorted(row, reverse=True)
col_ = sorted(col, reverse=True)
r = 0
for i in row_:
    if i != row_[0]:
        break
    r += 1
c = 0
for i in col_:
    if i != col_[0]:
        break
    c += 1
count = 0
for i in range(M):
    if row[hw[i][0] - 1] == row_[0] and col[hw[i][1] - 1] == col_[0]:
        count += 1
if r * c == count:
    print(row_[0] + col_[0] - 1)
else:
    print(row_[0] + col_[0])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, M = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * (H+1)
cnt_w = [0] * (W+1)
for _ in range(M):
    h, w = LI()
    bomb[(h, w)] = 1
    cnt_h[h] += 1
    cnt_w[w] += 1

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

ans = max_h + max_w

H_list = []
W_list = []
for i in range(1, H+1):
    if cnt_h[i] == max_h:
        H_list.append(i)

for i in range(1, W+1):
    if cnt_w[i] == max_w:
        W_list.append(i)

for w in W_list:
    for h in H_list:
        if bomb[(h, w)] == 0:
            print(ans)
            quit()
print(ans-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
HW = set()
for _ in range(m):
    x, y = map(int, input().split())
    HW.add((x-1,y-1))

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for h,w in HW:
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        if (h_ix, w_ix) in HW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

SHW = set()
for h,w in HW: SHW.add((h,w))

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        if (h_ix, w_ix) in SHW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)

Submission status: Accepted

Solution code:
import collections

h, w, m = map(int, input().split())
h_li = []
w_li = []

for i in range(m):
    _h, _w = map(int,input().split())
    h_li.append(_h)
    w_li.append(_w)

h_bomb = [0] * (h+1)
w_bomb = [0] * (w+1)

h_counter = collections.Counter(h_li)
w_counter = collections.Counter(w_li)

for i in range(1, h+1):
    h_bomb[i] = h_counter.get(i, 0)

for i in range(1, w+1):
    w_bomb[i] = w_counter.get(i, 0)
    
ans = max(h_bomb) + max(w_bomb)
allow_count = h_bomb.count(max(h_bomb)) * w_bomb.count(max(w_bomb))

s = 0
cnt = 0
for i in range(m):
    _h, _w = h_li[i], w_li[i]
    if h_bomb[_h] + w_bomb[_w] == ans:
        cnt += 1
    
if cnt < allow_count:
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(sorted(HW))
# print('---')
# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)
# print('====')

SHW = set()
for h,w in HW:
    SHW.add((h,w))
# print(SHW)

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        # if [h_ix, w_ix] in HW: continue
        if (h_ix, w_ix) in SHW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, M = map(int, rl().split())
    hw = [list(map(lambda n: int(n) - 1, rl().split())) for _ in range(M)]
    
    sum_h, sum_w = [0] * H, [0] * W
    for h, w in hw:
        sum_h[h] += 1
        sum_w[w] += 1
    max_h, max_w = max(sum_h), max(sum_w)
    cnt = sum_h.count(max_h) * sum_w.count(max_w)
    
    for h, w in hw:
        if sum_h[h] == max_h and sum_w[w] == max_w:
            cnt -= 1
    ans = max_h + max_w
    print(ans if cnt else ans - 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
  H, W, M = map(int, input().split())
  bomb = defaultdict(lambda: 0)
  lis_h = [0]*H
  lis_w = [0]*W
  for _ in range(M):
    h,w = map(int, input().split())
    h -= 1
    w -= 1
    bomb[(h,w)] = 1
    lis_h[h] += 1
    lis_w[w] += 1
  m_h = max(lis_h)
  m_w = max(lis_w)
  m_h_lis = []
  m_w_lis = []
  for i in range(H):
    if lis_h[i]==m_h:
      m_h_lis.append(i)
  for i in range(W):
    if lis_w[i]==m_w:
      m_w_lis.append(i)
  ans = 0
  for h in m_h_lis:
    for w in m_w_lis:
      if bomb[(h,w)]==0:
        return m_h+m_w
  return m_h+m_w-1
print(solve())

Submission status: Accepted

Solution code:
import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = np.zeros(h, dtype=int)
    col = np.zeros(w, dtype=int)
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    r = np.arange(h)[row == row.max()]
    c = np.arange(w)[col == col.max()]
    ans = row.max() + col.max()
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                print(ans)
                return
    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = [0] * h
    col = [0] * w
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    row_max = max(row)
    r = [i for i in range(h) if row[i] == row_max]
    col_max = max(col)
    c = [i for i in range(w) if col[i] == col_max]
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                print(row_max + col_max)
                return
    print(row_max + col_max - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0]*h
res2=[0]*w
for i in range(m):
    bomb1=bomb[i]
    res1[bomb1[0]-1]+=1
    res2[bomb1[1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=deque()
for j in range(h):
    res3=res1[j]
    if res3>s1:
            l1=[j+1]
            s1=res3
    elif res3==s1:
            l1.append(j+1)
s2=0
l2=deque()
for k in range(w):
    res4=res2[k]
    if res4>s2:
            l2=[k+1]
            s2=res4
    elif res4==s2:
            l2.append(k+1)
l3=set(l1)
l4=set(l2)
count=0

for l in range(m):
    bomb2=bomb[l]
    if bomb2[0] in l3 and bomb2[1] in l4:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

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

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            exit()

print(H_max + W_max -1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
            print(s)
            break
    if s == max_h_items[0][1] + max_w_items[0][1]:
        break
if s == max_h_items[0][1] + max_w_items[0][1] - 1:
    print(s)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
CW=set(CW)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        b=set(B[ch])
        if CW<=b:
            continue
        else:
            flag=1
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

Submission status: Accepted

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

h_target = [0]*(H+1)
w_target = [0]*(W+1)
target = []

for _ in range(M):
    h,w = map(int,input().split())
    target.append((h,w))
    h_target[h] += 1
    w_target[w] += 1

max_h = max(h_target)
max_w = max(w_target)

num_max_h = 0
num_max_w = 0

for i in h_target:
    if i == max_h:
        num_max_h += 1

for i in w_target:
    if i == max_w:
        num_max_w += 1

total = num_max_h*num_max_w # 最適地点の組み合わせ個数
point = 0 # 最適地点のうち爆破対象地点の個数

for i,j in target:
    if h_target[i] == max_h and w_target[j] == max_w:
        point += 1

if point == total:
    print(max_h+max_w-1)
else:
    print(max_h+max_w)

Submission status: Accepted

Solution code:
#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    h[i],w[i] = a-1,b-1


from collections import Counter
ch = Counter(h)
cw = Counter(w)

x_max=max(ch.values())
n_x_max = sum(ch[x]==x_max for x in range(H))
y_max=max(cw.values())
n_y_max = sum(cw[y]==y_max for y in range(W))
    
cnt =  sum(ch[h[i]]==x_max and cw[w[i]]==y_max for i in range(M))
if cnt < n_x_max*n_y_max:
    print(x_max+y_max)
else:
    print(x_max+y_max-1)

Submission status: Accepted

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

h_target = [0]*(H+1)
w_target = [0]*(W+1)
target = []

for _ in range(M):
    h,w = map(int,input().split())
    target.append((h,w))
    h_target[h] += 1
    w_target[w] += 1

max_h = max(h_target)
max_w = max(w_target)

num_max_h = 0
num_max_w = 0

for i in h_target:
    if i == max_h:
        num_max_h += 1

for i in w_target:
    if i == max_w:
        num_max_w += 1

total = num_max_h*num_max_w
point = 0

for i,j in target:
    if h_target[i] == max_h and w_target[j] == max_w:
        point += 1

if point == total:
    print(max_h+max_w-1)
else:
    print(max_h+max_w)

Submission status: Accepted

Solution code:
#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    h[i],w[i] = a-1,b-1

from collections import Counter
ch = Counter(h)
cw = Counter(w)

x_max=max(ch.values())
n_x_max = sum(ch[x]==x_max for x in range(H) if ch[x]==x_max)
y_max=max(cw.values())
n_y_max = sum(cw[y]==y_max for y in range(W) if cw[y]==y_max)
    
cnt =  sum(ch[h[i]]==x_max and cw[w[i]]==y_max for i in range(M))
if cnt < n_x_max*n_y_max:
    print(x_max+y_max)
else:
    print(x_max+y_max-1)

Submission status: Accepted

Solution code:
#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    h[i],w[i] = a-1,b-1


from collections import Counter
ch = Counter(h)
cw = Counter(w)

x_max=max(ch.values())
cand_x_max = [x for x in range(H) if ch[x]==x_max]

y_max=max(cw.values())
cand_y_max = [y for y in range(W) if cw[y]==y_max]

    
cnt=0
for i in range(M):
    if ch[h[i]]==x_max and cw[w[i]]==y_max:
        cnt+=1
if cnt<len(cand_x_max)*len(cand_y_max):
    print(x_max+y_max)
else:
    print(x_max+y_max-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m,k=map(int,input().split())
points=set()
row=defaultdict(int)
col=defaultdict(int)
for i in range(k):
    a,b=map(int,input().split())
    points.add((a,b))
    row[a]+=1
    col[b]+=1
m1=max(row.values())
m2=max(col.values())
l1=[]
l2=[]
for i in row:
    if row[i]==m1:
        l1.append(i)
for i in col:
    if col[i]==m2:
        l2.append(i)
ans=m2+m1-1
for i in l1:
    for j in l2:
        if (i,j) not in points:
           
            ans+=1
            print(ans)
            quit()
print(ans)

Submission status: Accepted

Solution code:
import sys

h,w,m = map(int, input().split( ))
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0]*h
Y = [0]*w
for a,b in bomb:
  X[a] += 1
  Y[b] += 1
maxX, maxY = max(X), max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

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:
import sys
input = sys.stdin.readline

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

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

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

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

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

# print(D,E)

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

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

Submission status: Accepted

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

horizontal = [[i,0] for i in range(H)]
vertical = [[i,0] for i in range(W)]
table = {}

for i in range(M):
    h,w = map(int,input().split())
    h -= 1
    w -= 1
    table[(h,w)] = True
    vertical[w][1] += 1
    horizontal[h][1] += 1

vertical.sort(key=lambda x:-x[1])
horizontal.sort(key = lambda x:-x[1])

h_max = horizontal[0][1]
v_max = vertical[0][1]
    
for i in range(H):
    if horizontal[i][1]<h_max:
        i -= 1
        break
for j in range(W):
    if vertical[j][1]<v_max:
        j -= 1
        break

flag = False
for h in horizontal[:i+1]:
    for v in vertical[:j+1]:
        if table.get((h[0],v[0]))==None:
            flag = True
            break
    if flag:
        break

if flag:
    print(h_max+v_max)
else:
    print(h_max+v_max-1)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
mine_h=[0]*H
mine_w=[0]*W
val=-1
mine=set()
for i in range(M):
    a,b=map(int,input().split())
    mine_h[a-1]+=1
    mine_w[b-1]+=1
    mine.add((a,b))
max_h=max(mine_h)
max_w=max(mine_w)
h_index=[i+1 for i, x in enumerate(mine_h)if x == max_h]
w_index=[i+1 for i, x in enumerate(mine_w)if x == max_w]
for i in h_index:
    for j in w_index:
        if (i,j) in mine:
            continue
        else:
            val=0
            break
print(max_h+max_w+val)

Submission status: Accepted

Solution code:
H, W, M, *hw = map(int, open(0).read().split())
H_cnt = [0] * (H + 1)
W_cnt = [0] * (W + 1)
bombs = [(h, w) for h, w in zip(*[iter(hw)] * 2)]
for h, w in bombs:
    H_cnt[h] += 1
    W_cnt[w] += 1

H_max_cnt = max(H_cnt)
W_max_cnt = max(W_cnt)

comb_cnt = H_cnt.count(H_max_cnt) * W_cnt.count(W_max_cnt)
for h, w in bombs:
    if H_cnt[h] == H_max_cnt and W_cnt[w] == W_max_cnt:
        comb_cnt -= 1

ans = H_max_cnt + W_max_cnt
print(ans if comb_cnt else ans - 1)

Submission status: Accepted

Solution code:
H, W, M, *hw = map(int, open(0).read().split())
H_cnt = [0] * (H + 1)
W_cnt = [0] * (W + 1)
bombs = [(h, w) for h, w in zip(*[iter(hw)] * 2)]
for h, w in bombs:
    H_cnt[h] += 1
    W_cnt[w] += 1

H_max_cnt = max(H_cnt)
W_max_cnt = max(W_cnt)

H_max = {i for i in range(1, H + 1) if H_cnt[i] == H_max_cnt}
W_max = {i for i in range(1, W + 1) if W_cnt[i] == W_max_cnt}

comb_cnt = len(H_max) * len(W_max)
for h, w in bombs:
    if H_cnt[h] == H_max_cnt and W_cnt[w] == W_max_cnt:
        comb_cnt -= 1

ans = H_max_cnt + W_max_cnt
print(ans if comb_cnt else ans - 1)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    h,w,m=map(int,input().split())
    hw=[list(map(int,input().split())) for i in range(m)]

    hlst=[[0,i] for i in range(h)]    
    wlst=[[0,i] for i in range(w)]
    dic={}
    for i in range(m):
        hh,ww=hw[i]
        hlst[hh-1][0]-=1
        wlst[ww-1][0]-=1
        dic[(hh-1,ww-1)]=1

    hlst.sort()
    wlst.sort()
    hkouho=[]
    wkouho=[]
    mi=0
    for i in range(h):
        if mi<hlst[i][0]:
            break
        hkouho.append(hlst[i][1])
        mi=hlst[i][0]
    mi=0
    for i in range(w):
        if mi<wlst[i][0]:
            break
        wkouho.append(wlst[i][1])
        mi=wlst[i][0]
    # print(hkouho)
    # print(wkouho)
    # print(hlst)
    for i in range(len(hkouho)):
        for j in range(len(wkouho)):
            if not (hkouho[i],wkouho[j]) in dic:
                print(-hlst[0][0]-wlst[0][0])
                exit()
    print(-hlst[0][0]-wlst[0][0]-1)
    # print(hkouho[0],wkouho[0])
main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

cnt_h = [0] * h #各行の爆破対象マス
cnt_w = [0] * w #各列の爆破対象マス
dic = defaultdict(int) #

for _ in range(m): #爆破対象のマスそれぞれ
  h_m, w_m = map(int, input().split()) #位置を取得
  cnt_h[h_m -1] += 1 #行のカウント
  cnt_w[w_m -1] += 1 #列のカウント
  dic[(h_m - 1, w_m - 1)] += 1 #マス（交差地点）を保持

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

mh = []
mw = []

for i in range(h):
  if max_h == cnt_h[i]:
    mh.append(i)
    
for j in range(w):
  if max_w == cnt_w[j]:
    mw.append(j)

for i in mh:
  for j in mw:
    if dic[(i, j)] == 0:
      print(max_h + max_w)
      exit()

print(max_h + max_w - 1)

Submission status: Accepted

Solution code:
from itertools import product
from sys import exit

def maxindexes(L,Lmax):
    ret = []
    for i in range(len(L)):
        if L[i] == Lmax:
            ret.append(i)
    
    return ret


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

for _ in range(M):
    a,b = (int(x)-1 for x in input().split())
    row[a] += 1
    col[b] += 1
    bomb.add((a,b))

rmax = max(row)
cmax = max(col)

rmaxind= maxindexes(row,rmax)
cmaxind = maxindexes(col,cmax)
prod = product(rmaxind,cmaxind)

for p in prod:
    if p not in bomb:
        print(rmax+cmax)
        exit(0)

print(rmax+cmax-1)

Submission status: Accepted

Solution code:
H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
bomb=[]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  bomb.append((h,w))

maxh=max(sumh)
maxw=max(sumw)
ch=sumh.count(maxh)
cw=sumw.count(maxw)

cnt=0
for h,w in bomb:
  if sumh[h-1]==maxh and sumw[w-1]==maxw:
    cnt+=1

if cnt==ch*cw:
  print(maxh+maxw-1)
else:
  print(maxh+maxw)

Submission status: Accepted

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

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

for i in range(m):
    hb, wb = map(int, input().split())
    h_bomb[hb-1] += 1
    w_bomb[wb-1] += 1
    bomb_list.append(tuple([hb, wb]))

h_bomb_max = max(h_bomb)
w_bomb_max = max(w_bomb)
h_bomb_line = []
w_bomb_line = []

for i in range(h):
    if h_bomb[i] == h_bomb_max:
        h_bomb_line.append(i)

for i in range(w):
    if w_bomb[i] == w_bomb_max:
        w_bomb_line.append(i)

bomb_set = set(bomb_list)

for i in h_bomb_line:
    for j in w_bomb_line:
        if (i+1, j+1) not in bomb_set:
            print(h_bomb_max+w_bomb_max)
            exit()

print(h_bomb_max + w_bomb_max -1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
se = set()
def ind(i,j):
    return i*w + j
for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    se.add((a-1,b-1))
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
# print(yl,xl,res)
for i in yl:
    for j in xl:
        if not (i,j) in se:
            res += 1
            print(res)
            quit()
print(res)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
h = []
w = []

for i in range(M):
    tmp1,tmp2 = map(int,input().split())
    h.append(tmp1)
    w.append(tmp2)

dic1 = {}
dic2 = {}

for i in h:
    if i not in dic1:
        dic1[i] = 1
    else:
        dic1[i] +=1

val1 = max(dic1,key=dic1.get)
ans = 0
ans +=dic1[val1]
for j in range(M):
    if h[j] != val1:
        if w[j] not in dic2:
            dic2[w[j]] = 1
        else:
            dic2[w[j]] +=1
if dic2:
    val2 = max(dic2,key=dic2.get)
    ans +=dic2[val2]


dic1 = {}
dic2 = {}

for i in w:
    if i not in dic1:
        dic1[i] = 1
    else:
        dic1[i] +=1
val1 = max(dic1,key=dic1.get)
ans1 = 0
ans1 +=dic1[val1]
for j in range(M):
    if w[j] != val1:
        if h[j] not in dic2:
            dic2[h[j]] = 1
        else:
            dic2[h[j]] +=1
if dic2:
    val2 = max(dic2,key=dic2.get)
    ans1 +=dic2[val2]
print(max(ans,ans1))

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 = [i+1 for i, x in enumerate(H) if x == hma]
w_index = [i+1 for i, x in enumerate(W) if x == wma]
val = -1
for j in range(len(h_index)):
    for k in range(len(w_index)):
        if (h_index[j],w_index[k]) in s:
            continue
        else:
            val = 0
            break
print(hma+wma+val)