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: Wrong Answer

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

maxr, maxc = Counter(), Counter()

mass = set()

for i in range(M):
    h, w = map(int, input().split())
    mass.add((h-1, w-1))
    maxr[h-1]+=1
    maxc[w-1]+=1

res = 0

m = 0 

for r, c in mass:
        res = max(res, maxr[r]+maxc[c] - int((r, c) in mass))
print(res)

Submission status: Wrong Answer

Solution code:
#pythran export main2()
import numpy as np
i4 = np.int32
i8 = np.int64


def solve(h, w, l, H, W, M):
    h_max = []
    w_max = []
    hm = h.max()
    wm = w.max()
    for i in range(H + 1):
        if h[i] == hm:
            h_max.append(i)
    for i in range(W + 1):
        if w[i] == wm:
            w_max.append(i)

    if len(h_max) * len(w_max) > M:
        return hm + wm

    for hj in h_max:
        for wj in w_max:
            if not wj in l[hj]:
                return hm + wm
    return hm + wm - 1


def main(in_file):
    stdin = open(in_file)
    H, W, M = [int(x) for x in stdin.readline().split()]
    h = np.zeros(H + 1, i8)
    w = np.zeros(W + 1, i8)
    l = [set() for _ in range(H + 1)]
    for _ in range(M):
        hi, wi = [int(x) for x in stdin.readline().split()]
        h[hi] += 1
        w[wi] += 1
        l[hi].add(wi)
    ans = solve(h, w, l, H, W, M)
    print(ans)


def main2():
    main('/dev/stdin')

Submission status: Wrong Answer

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if not [i,j] in object:
            ans = h_max + w_max
            break
            break
            
else:
   ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
if H==1 and W == 1:
  print(1)
  exit()
hwlist = [list(map(int, input().split())) for i in range(M)]
a = []
b = []
for h in range(H):
    a.append(0)
for w in range(W):
    b.append(0)
for m in range(M):
  a[hwlist[m][0]-1] += 1
  b[hwlist[m][1]-1] += 1
max_a = max(a)
a_max_id = [i for i, v in enumerate(a) if v == max_a]
max_b = max(b)
b_max_id = [i for i, v in enumerate(b) if v == max_b]
for i in range(len(a_max_id)):
  for j in range(len(a_max_id)):
    if not [a_max_id, b_max_id] in hwlist:
      print(max_a + max_b)
      exit()
print(max_a + max_b - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
'''
m = np.zeros((H, W))
'''
ans = 3
'''
for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[tmp_h-1, tmp_w-1] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if m[i[0]][j[0]] == 1.:
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp
'''
print(int(ans))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w,m=map(int,input().split())
l={}
u={}
hw=[list(map(int,input().split())) for _ in range(m)]
sl=set()
for i in range(m):
    hr,wr=hw[i]
    if hr-1 in u:
        u[hr-1]+=1
    else:
        u[hr-1]=1
    if wr-1 in l:
        l[wr-1]+=1
    else:
        l[wr-1]=1
    
    sl.add((hr-1)*w+(wr-1))
resl=0
resu=0
cl=set()
cu=set()
for i in l:
    if resl<l[i]:
        resl=l[i]
        cl=set([i])
    elif resl==l[i]:
        cl.add(i)
for i in u:
    if resu<u[i]:
        resu=u[i]
        cu=set([i])
    elif resu==u[i]:
        cu.add(i)
ans=0
for i in range(m):
  hr,wr=hw[i]
  if wr-1 in cl and hr-1 in cu:
    cl.remove(wr-1)
    cu.remove(hr-1)
if not cu|cl:
  print(resu+resl-1)
else:
  print(resu+resl)

Submission status: Wrong Answer

Solution code:
H,W,M = map(int,input().split())
L = [[0 for _ in range(W)] for _ in range(H)]
B = []
for i in range(M):
    h,w = map(int,input().split())
    L[h-1][w-1] += 1
    B.append([h-1,w-1])
y = 0
yy = 0
yl = []
t = 0
tt = 0
tl = []
for i in range(H):
    a = sum(L[i])
    if a > y:
        y = a
        yy = i
        yl = [i]
    elif a == y:
        yl.append(i)
R = list(zip(*L))
for i in range(W):
    b = sum(R[i])
    if b > t:
        t = b
        tt = i
        tl = [i]
    elif b == t:
        tl.append(i)
if len(yl) == 1 and len(tl) != 1:
    for i in range(len(tl)):
        if L[yy][tl[i]] == 0:
            tt = tl[i]
            break
elif len(tl) == 1 and len(yl) != 1:
    for i in range(len(yl)):
        if L[yl[i]][tt] == 0:
            yy = yl[i]
elif len(yl) != 1 and len(tl) != 1:
    for i in range(M):
        if B[i][0] in yl and B[i][1] in tl:
            yy = B[i][0]
            tt = B[i][1] 
if L[yy][tt] == 1:
    print(y + t - 1)
else:
    print(y + t)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, M = map(int, input().split())
'''
h = np.zeros(H)
w = np.zeros(W)
m = np.zeros((H, W))
'''
ans = 3
'''
for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[tmp_h-1, tmp_w-1] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if m[i[0]][j[0]] == 1.:
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp
'''
print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

for _ in range(M):
    tmp_h,tmp_w = map(int,input().split())
    h.append(tmp_h)
    w.append(tmp_w)
    S.append((tmp_h,tmp_w))

H_count = Counter(h).most_common()
W_count = Counter(w).most_common()
flag = True


for a,b in S:
    if (H_count[0][1],W_count[0][1]) == (a,b):
        flag = False
print(H_count[0][1] + W_count[0][1] if flag else H_count[0][1] + W_count[0][1] - 1)

Submission status: Wrong Answer

Solution code:
import sys
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxCount]
if maxCount==0:
  print(0)
  sys.exit(0)


maxCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxCount]

#counterList = []
#for maxH in maxHList:
#  for maxW in maxWList:
#    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
#print(max(counterList))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))
for maxH, maxW in ((maxH, maxW) for maxH in maxHList for maxW in maxWList):
	if (maxH, maxW) in pList:
		print(hList[maxH] + wList[maxW] - 1)
		sys.exit(0)

print(hList[maxH] + wList[maxW])

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

    g = [0]*h
    r = [0]*w
    ba = []
    for _ in range(m):
        s,t = map(int,input().split())
        g[s-1] += 1
        r[t-1] += 1
        ba.append((s-1,t-1))

    a = g.index(max(g))
    b = r.index(max(r))
    if (a,b) in ba:
        print(max(g) + max(r) - 1)
    else:
        print(max(g) + max(r))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys,random

input=sys.stdin.readline

H,W,M=map(int,input().split())
bomb=[[] for i in range(H)]
row=[0 for i in range(H)]
column=[0 for j in range(W)]

for _ in range(M):
    h,w=map(int,input().split())
    #h,w=random.randint(1,H),random.randint(1,W)
    row[h-1]+=1
    column[w-1]+=1
    bomb[h-1].append(w-1)

for i in range(H):
    bomb[i].sort()

Seg=SegmentTree(column,segfunc=max,ide_ele=0)

ans=0
for i in range(H):
    for j in range(len(bomb[i])-1):
        L,R=bomb[i][j],bomb[i][j+1]
        tmp=row[i]+max(column[L],column[R])-1
        ans=max(ans,tmp)
        L+=1
        if L==R:
            continue
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if bomb[i] and bomb[i][0]!=0:
        L,R=0,bomb[i][0]
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if bomb[i] and bomb[i][-1]!=W-1:
        L,R=bomb[i][-1]+1,W
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if not bomb[i]:
        tmp=row[i]+Seg.query(0,W)
        ans=max(ans,tmp)

print(ans)

Submission status: Wrong Answer

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

H=[0]*h
W=[0]*w
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

for mine in M:
    if mine[0]-1 in maxhindex and mine[1]-1 in maxwindex:
        end=1
    else:
        end=0
        break

ans=maxh+maxw
if end==1:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, m = map(int, input().split())
h_list = [0] * h
w_list = [0] * w
lw = []
for i in range(m):
    h_tmp, w_tmp = map(int, input().split())
    h_list[h_tmp - 1] += 1
    w_list[w_tmp - 1] += 1
    lw.append(w_tmp)
mh = max(h_list)
id = h_list.index(mh)
mw = max(w_list)
# print(id)
if id+1 in lw:
    print(mh + mw - 1)
else:
    print(mh + mw)

Submission status: Wrong Answer

Solution code:
H,W,M=map(int,input().split())
HS=[0 for _ in range(H)]
WS=[0 for _ in range(W)]
S=[[0 for _ in range(W)] for _ in range(H)]
answers=[]
for _ in range(M):
    h,w=map(int,input().split())
    answers.append([h-1,w-1])
    S[h - 1][w - 1] += 1
    HS[h-1]+=1
    WS[w-1]+=1

Submission status: Wrong Answer

Solution code:
import numpy as np
'''
H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = np.zeros((H, W))
'''
ans = 3
'''
for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[tmp_h-1, tmp_w-1] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if m[i[0]][j[0]] == 1.:
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp
'''
print(int(ans))

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
hwlist = [list(map(int, input().split())) for i in range(M)]
a = []
b = []
for h in range(H):
    a.append(0)
for w in range(W):
    b.append(0)
for m in range(M):
  a[hwlist[m][0]-1] += 1
  b[hwlist[m][1]-1] += 1
max_a = max(a)
a_max_id = [i for i, v in enumerate(a) if v == max_a]
max_b = max(b)
b_max_id = [i for i, v in enumerate(b) if v == max_b]
for i in range(len(a_max_id)):
  for j in range(len(a_max_id)):
    if not [a_max_id, b_max_id] in hwlist:
      print(max_a + max_b)
      exit()
print(max_a + max_b - 1)

Submission status: Wrong Answer

Solution code:
H, W, M = list(map(int, input().split()))
HW = set()
hd = {}
wd = {}
for i in range(M):
	h, w = tuple(map(int, input().split()))
	HW.add((h, w))
	if h in hd:
		hd[h] += 1
	else:
		hd[h] = 1
	if w in wd:
		wd[w] += 1
	else:
		wd[w] = 1

h = max(hd, key=hd.get)
w = max(wd, key=wd.get)
ans = 0
if (h, w) in HW:
	ans = hd[h] + wd[w] - 1
else:
	ans = hd[h] + wd[w]
print(ans)

Submission status: Wrong Answer

Solution code:
*q,k=map(int,input().split())
d={}
f={}
D=[0]*k
F=[0]*k
cnt=0
for i in range(k):
    h,w=map(int,input().split())
    if not h in d:
        d[h]=1
    else:
        d[h] = 1+d[h]
    if not w in f:
        f[w]=1
    else:
        f[w]=f[w]+1
    D[i]=h
    F[i]=w
dk=max(d,key=d.get)
fk=max(f,key=f.get)
for i in range(k):
    if D[i]==dk and F[i]==fk:
        cnt+=1
print(d[dk]+f[fk]-cnt)

Submission status: Wrong Answer

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

H=[0]*h
W=[0]*w
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

end=0

for mine in M:
    if mine[0]-1 in maxhindex and mine[1]-1 in maxwindex:
        end=1
    else:
        break

ans=maxh+maxw
if end==1:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = {}
for i in range(M):
    h, w = map(int, input().split())
    t[(h-1, w-1)] = 1
    h_t[h-1]+=1
    w_t[w-1]+=1
print(t)
h_max = max(h_t)
h_max_list = [i for i in range(len(h_t)) if h_t[i] == h_max]
w_max = max(w_t)
w_max_list = [i for i in range(len(w_t)) if w_t[i] == w_max]

for h in h_max_list:
    for w in w_max_list:
        if (h, w) not in t:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

Submission status: Wrong Answer

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

mat=[[0 for r in range(W) ] for l in range(H)]

heightDi=defaultdict(int)
widthDi=defaultdict(int)

bombs=[]
for i in range(M):
  h,w=[int(r) for r in input().split()]
  bombs.append([h,w])
  heightDi[h]+=1
  widthDi[w]+=1

maxtmpH=0
maxtmpW=0
sum=0
for a,b in bombs:
  sum=max(heightDi[a]+widthDi[b]-1,sum) if [a,b] in bombs else max(heightDi[a]+widthDi[b],sum)
print(sum)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]
tate, yoko = defaultdict(int), defaultdict(int)
for h, w in hw:
    tate[h] += 1
    yoko[w] += 1
tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_max, yoko_max = tate[0][1], yoko[0][1]
max_tates, max_yokos = [], []
for t in tate:
    if t[1] == tate_max:
        max_tates.append(t)
    else:
        break
for y in yoko:
    if y[1] == yoko_max:
        max_yokos.append(y)
    else:
        break
ans = [i[0] for i in max_tates]
ans_ = [j[0] for j in max_yokos]

for h, w in hw:
    if h in ans and w in ans_:
        print(tate_max + yoko_max - 1)
        break
else:
    print(tate_max + yoko_max)

Submission status: Wrong Answer

Solution code:
h,w,m=map(int, input().split())
H=[0]*h
W=[0]*w
A=[]
B=[]
for i in range(m):
	a,b=map(int, input().split())
	H[a-1]+=1
	W[b-1]+=1
	A.append(a)
	B.append(b)

HH=set()
WW=set()
for i in range(h):
	if H[i]==max(H):
		HH.add(i+1)

for i in range(w):
	if W[i]==max(W):
		WW.add(i+1)

for i in range(m):
	if A[i] not in HH and B[i] not in WW:
		print(max(H)+max(W))
		exit()
print(A)
print(B)
print(HH)
print(WW)
print(max(H)+max(W)-1)

Submission status: Wrong Answer

Solution code:
#E
import os
import sys
import numpy as np
from collections import Counter

def main():
    # height, width, m = map(int, input().split())
    # h = [0] * m
    # w = [0] * m
    # for i in range(m):
    #     h[i], w[i] = map(int, input().split())
    height = inp[0]
    width = inp[1]
    m = inp[2]
    h = inp[3::2] - 1
    w = inp[4::2] - 1
    
    ch = Counter()
    ch.update(h)
    cw = Counter()
    cw.update(w)
    
    row = int(ch.most_common()[0][0])
    col = int(cw.most_common()[0][0])
    
    flag = False
    index = np.where(h == row)
    l = len(index)
    for i in range(l):
        if w[index[0][i]] == col:
            flag = True
        
    
    if flag:
        print(ch.most_common()[0][1] + cw.most_common()[0][1] - 1)
    else:
        print(ch.most_common()[0][1] + cw.most_common()[0][1])
    
if __name__ == "__main__":
    if os.name == 'posix':
        # noinspection PyUnresolvedReferences
        #from my_module import solve
        1
    else:
        from numba import njit
     
        solve = njit('(i8[:],)', cache=True)(solve)
        print('compiled', file=sys.stderr)
     
    inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
    
    # ans = solve(inp)
    # print('\n'.join(map(str, ans)))
    
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys,random

input=sys.stdin.readline

H,W,M=map(int,input().split())
bomb=[[] for i in range(H)]
row=[0 for i in range(H)]
column=[0 for j in range(W)]

for _ in range(M):
    h,w=map(int,input().split())
    #h,w=random.randint(1,H),random.randint(1,W)
    row[h-1]+=1
    column[w-1]+=1
    bomb[h-1].append(w-1)

for i in range(H):
    bomb[i].sort()

Seg=SegmentTree(column,segfunc=max,ide_ele=-1)

ans=0
for i in range(H):
    for j in range(len(bomb[i])-1):
        L,R=bomb[i][j],bomb[i][j+1]
        tmp=row[i]+max(column[L],column[R])-1
        ans=max(ans,tmp)
        L+=1
        if L==R:
            continue
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if bomb[i] and bomb[i][0]!=0:
        L,R=0,bomb[i][0]
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if bomb[i] and bomb[i][-1]!=W-1:
        L,R=bomb[i][-1]+1,W
        tmp=row[i]+Seg.query(L,R)
        ans=max(ans,tmp)
    if not bomb[i]:
        tmp=row[i]+Seg.query(0,W)
        ans=max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,M = list(map(int, input().split()))
s = []
Hlist = [0 for i in range(H)]
Wlist = [0 for i in range(W)]
for i in range(M):
  s.append(list(map(int, input().split())))
  Hlist[s[i][0]-1] += 1
  Wlist[s[i][1]-1] += 1
  
Hmax = max(Hlist)
Wmax = max(Wlist)
Hmaxindex = [i for i, v in enumerate(Hlist) if v == Hmax]
Wmaxindex = [i for i, v in enumerate(Wlist) if v == Wmax]

plusoneflag = 0
for i in range(len(Hmaxindex)):
  for j in range(len(Wmaxindex)):
    templist = [Hmaxindex[i]+1,Wmaxindex[j]+1]
    if(templist in s):
      plusoneflag = 1
      break
  if(plusoneflag == 1):
    break

if(plusoneflag == 1):
  print(Hmax + Wmax - 1)
else:
  print(Hmax + Wmax)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w,m=map(int,input().split())
l={}
u={}
hw=[list(map(int,input().split())) for _ in range(m)]
sl=set()
for i in range(m):
    hr,wr=hw[i]
    if hr-1 in u:
        u[hr-1]+=1
    else:
        u[hr-1]=1
    if wr-1 in l:
        l[wr-1]+=1
    else:
        l[wr-1]=1
    
    sl.add((hr-1)*w+(wr-1))
resl=0
resu=0
cl=set()
cu=set()
for i in l:
    if resl<l[i]:
        resl=l[i]
        cl=set([i])
    elif resl==l[i]:
        cl.add(i)
for i in u:
    if resu<u[i]:
        resu=u[i]
        cu=set([i])
    elif resu==u[i]:
        cu.add(i)
ans=0
for i in range(m):
  hr,wr=hw[i]
  if wr-1 in cl:
    cl.remove(wr-1)
  if hr-1 in cu:
    cu.remove(hr-1)
if not cu|cl:
  print(resu+resl-1)
else:
  print(resu+resl)

Submission status: Wrong Answer

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

H=[0]*h
W=[0]*w
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

end=0

for mine in M:
    if mine[0]-1 in maxhindex and mine[1]-1 in maxwindex:
        end=1

ans=maxh+maxw
if end==1:
    ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, m = map(int, input().split())
boms = [[0,0] for i in range(m)]
Hs = [0] * h
Ws = [0] * w
for i in range(m):
  _h, _w = map(int, input().split())
  boms[i][0] = _h - 1
  boms[i][1] = _w - 1
  Hs[_h - 1] += 1
  Ws[_w - 1] += 1
Hmax = max(Hs)
Hcount = Hs.count(Hmax)
Wmax = max(Ws)
Wcount = Ws.count(Wmax)
Hindexs = [0] * Hcount
Windexs = [0] * Wcount
hcount = 0
wcount = 0
for i in range(h):
  if Hs[i] == Hmax:
    Hindexs[hcount] = i
    hcount += 1
for i in range(w):
  if Ws[i] == Wmax:
    Windexs[wcount] = i
    wcount += 1
count = 0

Submission status: Wrong Answer

Solution code:
h,w,m=map(int,input().split())
r=dict()
c=dict()
pos=[]
rmax=0
cmax=0
for i in range(m):
    row,col=map(int,input().split())
    if(row in r):
        r[row]+=1
        rmax=max(r[row],rmax)
    else:
        r[row]=1
        rmax=max(r[row],rmax)
    if(col in c):
        c[col]+=1
        cmax=max(c[col],cmax)
    else:
        c[col]=1
        cmax=max(c[col],cmax)
    pos.append(str(row)+str(col))
    
sorted(r.items(),key=lambda x:x[1])
sorted(c.items(),key=lambda x:x[1])
ans=-100
for i in r.keys():
    if(i<rmax):
        continue
    for j in c.keys():
        if(j<cmax):
            continue
        tmp=r[i]+c[j]
        if((str(i)+str(j)) in pos):
            tmp-=1
        ans=max(ans,tmp)
        
print(ans)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
import numpy as np
from  collections import Counter

hw = np.zeros(
  (M, 2),np.uint8
)
for _ in range(M):
  h, w = map(int, input().split())
  hw[_][0] = h
  hw[_][1] = w
  
#print(hw, hw[:, 0])
c_h = Counter(hw[:, 0]).most_common()
c_w = Counter(hw[:, 1]).most_common()

max_ch = c_h[0][1]
max_ch_lst = []
for _c_h in c_h:
  if _c_h[1] == max_ch:
    max_ch_lst.append(_c_h[0])
  else:
    break
    
max_cw = c_w[0][1]
max_cw_lst = []
flg = 1
for _c_w in c_w:
  if _c_w[1] == max_cw:
    #max_cw_lst.append(_c_w[0])
    for k in max_ch_lst:
      if [k, _c_w[0]] not in hw:
        flg = 0
        break
  else:
    break
if max_ch == 1 or max_cw == 1:
  flg = 0
print(max_cw + max_ch -flg)
#print(max_cw, max_ch)

Submission status: Wrong Answer

Solution code:
h, w, m = map(int, input().split())
boms = [[0,0] for i in range(m)]
Hs = [0] * h
Ws = [0] * w
for i in range(m):
  _h, _w = map(int, input().split())
  boms[i][0] = _h - 1
  boms[i][1] = _w - 1
  Hs[_h - 1] += 1
  Ws[_w - 1] += 1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h,w,m = LI()
    hw = LIR(m)
    # h, w, m = [3 * 10 ** 5] * 3
    # hw = [(i, i) for i in range(3 * 10 ** 5)]
    dh = defaultdict(int)
    dh1 = defaultdict(int)
    dw = defaultdict(int)
    dw1 = defaultdict(int)
    ma = defaultdict(int)
    for hi, wi in hw:
        dh[hi] += 1
        dw[wi] += 1
        ma[(hi, wi)] = 1
    maxh = max(dh.values())
    maxw = max(dw.values())
    for key, value in dh.items():
        if value == maxh:
            dh1[key] = maxh
    for key, value in dw.items():
        if value == maxw:
            dw1[key] = maxw
    for hi, wi in hw:
        if wi in dw1:
            dw1[wi] -= 1
    if maxw == max(dw1.values()):
        print(maxh + maxw)
        return
    for hi, wi in hw:
        if hi in dh1:
            dh1[hi] -= 1
    if maxh == max(dh1.values()):
        print(maxh + maxw)
        return
    
    print(maxh + maxw - 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = {}
for i in range(M):
    h, w = map(int, input().split())
    t[(h-1, w-1)] = 1
    h_t[h-1]+=1
    w_t[w-1]+=1
h_max = max(h_t)
h_max_list = [i for i in range(len(h_t)) if h_t[i] == h_max]
w_max = max(w_t)
w_max_list = [i for i in range(len(w_t)) if w_t[i] == w_max]

for h in h_max_list:
    for w in w_max_list:
        if (h, w) in t:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

Submission status: Wrong Answer

Solution code:
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
 
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
#leftkeys = [k for k, v in countleft.items() if v == leftmax]
#rightkeys = [k for k, v in countright.items() if v == rightmax]
leftkeys = (list(countleft.keys())[list(countleft.values()).index(leftmax)])
rightkeys = (list(countright.keys())[list(countright.values()).index(rightmax)])
 
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)

for i in range(leftkeyN):
    if flag != 0:
        break
    else:
        for P in range(rightkeyN):
            for T in range(M):
                if c[T] == [leftkeys[i],rightkeys[P]]:
                    cnt = cnt + 1
            if cnt == 0:
                flag = flag + 1
                break
            else:
                cnt = 0
 
if flag == 0:
    print(int(tempmax - 1))
else:
    print(int(tempmax))

Submission status: Wrong Answer

Solution code:
from sys import exit, stdin

# import copy
from collections import deque, Counter

# import numpy as np
input = stdin.readline

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

col = Counter()
row = Counter()
D = Counter()
for i in range(M):
    h, w = map(int, input().split())
    row.update([h])
    col.update([w])
    D.update([str(h) + str(w)])

# rmax = row.most_common(1)
# cmax = col.most_common(1)
# idx = str(rmax[0][0]) + str(cmax[0][0])
# p = D[idx]

# ans = rmax[0][1] + cmax[0][1] - p

rtmp = row.most_common(1)[0][1]
ctmp = col.most_common(1)[0][1]
rmax = []
cmax = []

for r in row.most_common():
    if r[1] < rtmp:
        break
    rmax.append(r)

for c in col.most_common():
    if c[1] < ctmp:
        break
    cmax.append(c)

ridx = str(rmax[0][0])
for d in cmax:
    if D[ridx + str(d[0])] == 0:
        ans = rmax[0][1] + d[1]
        break
else:
    ans = rmax[0][1] + d[1] - 1


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, m = map(int, input().split())
M = [list(map(int, input().split())) for i in range(m)]

H=[0]*h
W=[0]*w
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1

    print(mine)

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

end=0

for mine in M:
    if mine[0]-1 in maxhindex and mine[1]-1 in maxwindex:
        end=1

ans=maxh+maxw
if end==0:
    ans-=1
print(ans)