Problem:


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

H, W, M = map(int, input().split())
raw = defaultdict(int)
col = defaultdict(int)
hw = set()
for i in range(M):
    h, w = map(int, stdin.readline().split())
    raw[h] += 1
    col[w] += 1
    hw.add((h, w))
mh = max(raw.values())
mw = max(col.values())
rawkey = [h for h in raw.keys() if raw[h] == mh]
colkey = [w for w in col.keys() if col[w] == mw]
for h in rawkey:
    for w in colkey:
        if (h, w) not in hw:
            print(mh + mw)
            exit()
print(mh + mw -1)

Submission status: Accepted

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
count_row = Counter()
count_col = Counter()
count_point = Counter()
for i in range(M):
    h, w = map(int, input().split())
    count_row[h] += 1
    count_col[w] += 1
    count_point[(h, w)] += 1

max_h, max_count_row = count_row.most_common()[0]
max_w, max_count_col = count_col.most_common()[0]
row_iter = [h for h, c in count_row.most_common() if c == max_count_row]
col_iter = [w for w, c in count_col.most_common() if c == max_count_col]
ans = max_count_row + max_count_col - 1
flag = False
for h in row_iter:
    for w in col_iter:
        if count_point[(h, w)] == 1:
            continue
        ans += 1
        flag = True
        break
    if flag:
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

hlst=[x for x,_ in hw]
wlst=[x for _,x in hw]

hcnt=Counter(hlst)
wcnt=Counter(wlst)

_,hmax=hcnt.most_common(1)[0]
_,wmax=wcnt.most_common(1)[0]
hcand=set([k for k,v in hcnt.items() if v==hmax])
wcand=set([k for k,v in wcnt.items() if v==wmax])

ng=[(hh,ww) for hh,ww in hw if ((hh in hcand) and (ww in wcand))]

if len(hcand)*len(wcand)>len(ng):
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Accepted

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

hlst=[x for x,_ in hw]
wlst=[x for _,x in hw]

hcnt=Counter(hlst)
wcnt=Counter(wlst)


_,hmax=hcnt.most_common(1)[0]
_,wmax=wcnt.most_common(1)[0]
hcand=set([k for k,v in hcnt.items() if v==hmax])
wcand=set([k for k,v in wcnt.items() if v==wmax])

ng=[]

for hh,ww in hw:
    if hh in hcand and ww in wcand:
        ng.append((hh,ww))

if len(hcand)*len(wcand)>len(ng):
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve():
    from collections import defaultdict
    H, W, M = map(int, input().split())
    hcount = defaultdict(int)
    wcount = defaultdict(int)
    bombs = set()
    for _i in range(M):
        h, w = map(int, input().split())
        hcount[h] += 1
        wcount[w] += 1
        bombs.add((h, w))

    maxh = max(hcount.values())
    maxw = max(wcount.values())
    hs = [k for k in hcount if hcount[k] == maxh]
    ws = [k for k in wcount if wcount[k] == maxw]
    if len(hs) * len(ws) > M:
        return maxh + maxw
    for h in hs:
        for w in ws:
            if (h, w) not in bombs:
                return maxh + maxw
    return maxh + maxw - 1


def main():
    print(solve())


# tests
T1 = """
2 3 3
2 2
1 1
1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
3 3 4
3 3
3 1
1 1
1 2
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
3
"""

T3 = """
5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

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

hl, wl = [0]*H, [0]*W
for i,j in A:
    hl[i-1] += 1
    wl[j-1] += 1

mt,mh = max(hl),max(wl)

a = 0
for i,j in A:
    if hl[i-1] == mt and wl[j-1] == mh:
        a += 1

print(mt+mh-1 if a == hl.count(mt) * wl.count(mh) else mt+mh)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(H, W, XY):
    U = 300_010
    row = np.zeros(U, np.int64)
    col = np.zeros(U, np.int64)
    
    for i in range(0, len(XY), 2):
        x, y = XY[i:i+2]
        row[x] += 1 ; col[y] += 1

    row_max = row.max() ; col_max = col.max()
    choice = np.sum(row == row_max) * np.sum(col == col_max)
    for i in range(0, len(XY), 2):
        x, y = XY[i:i+2]
        if row[x] == row_max and col[y] == col_max:
            choice -= 1
    ans = row_max + col_max
    return ans if choice else ans-1



H, W, M = map(int, readline().split())
XY = np.array(read().split(), np.int64)

print(main(H, W, XY))

Submission status: Accepted

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

takasa = [0]*(H)
haba = [0]*(W)

for i in range(M):
    takasa[A[i][0]-1] += 1
    haba[A[i][1]-1] += 1

mt = max(takasa)
mh = max(haba)
ct = takasa.count(mt)
ch = haba.count(mh)

a = 0
for i in range(M):
    if takasa[A[i][0]-1] == mt and haba[A[i][1]-1] == mh:
        a += 1

if a == ct*ch:
    print(mt+mh-1)
else:
    print(mt+mh)

Submission status: Accepted

Solution code:
from collections import Counter

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

hlst=[x for x,_ in hw]
wlst=[x for _,x in hw]

hcnt=Counter(hlst)
wcnt=Counter(wlst)

_,hmax=hcnt.most_common(1)[0]
_,wmax=wcnt.most_common(1)[0]

hcand=set()
wcand=set()

for k,v in hcnt.items():
    if v==hmax:
        hcand.add(k)

for k,v in wcnt.items():
    if v==wmax:
        wcand.add(k)

ng=set()

for hh,ww in hw:
    if hh in hcand and ww in wcand:
        ng.add((hh,ww))

if len(hcand)*len(wcand)>len(ng):
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Accepted

Solution code:
from collections import Counter
H, W, M = [int(i) for i in input().split()]
g = set()
h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = [int(j) for j in input().split()]
    g.add((h[i],w[i]))

ch = Counter(h)
cw = Counter(w)

chm = max(ch.values())
cwm = max(cw.values())
hi = [i for i in ch.keys() if ch[i] == chm]
wi = [i for i in cw.keys() if cw[i] == cwm]

for i in hi:
    for j in wi:
        if (i,j) not in g:
            print(ch[i] + cw[j])
            exit()
print(ch[hi[0]] + cw[wi[0]] - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

h,w,m= LI()
s=set()
D1=defaultdict(int)
D2=defaultdict(int)
for _ in range(m):
    h,w=LI()
    D1[h-1]+=1
    D2[w-1]+=1
    s.add((h-1,w-1))

h_max = max(D1.values())
w_max = max(D2.values())
A=[i for i,v in D1.items() if v==h_max]
B=[i for i,v in D2.items() if v==w_max]

flg = 1
for i in A:
    for j in B:
        if (i, j) not in s:
            flg = 0
            break

print(w_max+h_max-flg)

Submission status: Accepted

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

hc = [0] * H
wc = [0] * W
d = {}
for _ in range(M):
    h, w = map(lambda x: int(x) - 1,input().split())
    hc[h] += 1
    wc[w] += 1
    d[(h, w)] = 1

maxh = max(hc)
maxw = max(wc)

result = maxh + maxw - 1
wi = [i for i in range(W) if wc[i] == maxw]
for h in [i for i in range(H) if hc[i] == maxh]:
    for w in wi:
        if (h, w) not in d:
            result = maxh + maxw
            break
print(result)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
hw = [list(map(int, input().split())) for i in range(m)]
hl, wl = [0] * (h + 1), [0] * (w + 1)
for i in hw:
    hl[i[0]] += 1
    wl[i[1]] += 1
hm, wm = max(hl), max(wl)
cnt = hl.count(hm) * wl.count(wm)
for i, j in hw:
    if hl[i] + wl[j] == hm + wm:
        cnt -= 1
print(hm + wm if cnt > 0 else hm + wm - 1)

Submission status: Accepted

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
h = [0] * M
w = [0] * M
h_w = {}
for i in range(M):
    h[i], w[i] = map(int, input().split())
    h_w[(h[i], w[i])] = 1
hl = Counter(h)
hl = list(reversed(sorted(hl.items(), key=lambda x:x[1])))
wl = Counter(w)
wl = list(reversed(sorted(wl.items(), key=lambda x:x[1])))
ans = 0
#print(hl)
#print(wl)
max_hl = hl[0][1]
max_wl = wl[0][1]
ans = max_hl + max_wl
end_flag = 0
max_flag = 1
for i in range(len(hl)):
    for j in range(len(wl)):
        if hl[i][1] < max_hl:
            end_flag = 1
            break
        if wl[j][1] < max_wl:
            break
        if (hl[i][0], wl[j][0]) in h_w.keys():
            continue
        else:
            end_flag = 1
            max_flag = 0
            break
    else:
        continue
    if end_flag == 1:
        break
print(ans - max_flag)

Submission status: Accepted

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

hc = [0] * H
wc = [0] * W
d = {}
for _ in range(M):
    h, w = map(lambda x: int(x) - 1,input().split())
    hc[h] += 1
    wc[w] += 1
    d[(h, w)] = 1

maxh = max(hc)
maxw = max(wc)

result = max(maxh + maxw - 1, 0)
wi = [i for i in range(W) if wc[i] == maxw]
for h in [i for i in range(H) if hc[i] == maxh]:
    for w in wi:
        if (h, w) not in d:
            result = maxh + maxw
            break
print(result)

Submission status: Accepted

Solution code:
import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = x.count(mx)
y1 = y.count(my)
z1 = x1 * y1
for i, j in z:
    if x[i] == mx and y[j] == my:
        z1 -= 1
if z1: print (mx + my)
else: print (mx + my - 1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

h,w,m= LI()
s=set()
D1=defaultdict(int)
D2=defaultdict(int)
for _ in range(m):
    h,w=LI()
    D1[h-1]+=1
    D2[w-1]+=1
    s.add((h-1,w-1))

A=[[v,i] for i,v in D1.items()]+[[-INF,-INF]]
B=[[v,i] for i,v in D2.items()]+[[-INF,-INF]]
A.sort(reverse=True)
B.sort(reverse=True)
a_now=0
b_now=0
ans=-INF
while True:
    av,ak=A[a_now]
    bv,bk = B[b_now]
    ans=max(ans,av+bv-int((ak,bk) in s))
    if a_now==len(A)-2 and b_now==len(B)-2:
        break
    elif A[a_now+1][0]+B[b_now][0]>A[a_now][0]+B[b_now+1][0]:
        a_now+=1
    else:
        b_now+=1

print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]
hw_set = set()
for bomb in hw:
    hw_set.add((bomb[0], bomb[1]))
h_value = [0]*(H+1)
w_value = [0]*(W+1)
# exist = [ [0 for _ in range(W+1)] for _ in range(H+1)]

for coordinate in hw:
    h_value[coordinate[0]] += 1
    w_value[coordinate[1]] += 1
    

h_max = max(h_value)
w_max = max(w_value)

h_max_ind = list()
w_max_ind = list()
h_max_ind_num = 0
w_max_ind_num = 0

for i in range(H+1):
    if h_value[i] == h_max:
        h_max_ind.append(i)
        h_max_ind_num += 1


for i in range(W+1):
    if w_value[i] == w_max:
        w_max_ind.append(i)
        w_max_ind_num += 1

# print("put", h_max_ind, w_max_ind)
flag = False
if (h_max_ind_num * w_max_ind_num) > M:
    flag = True
else:
    for h in h_max_ind:
        for w in w_max_ind:
            if not (h, w) in hw_set:
                flag = True
                break

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

Submission status: Accepted

Solution code:
# import numpy as np

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

h_array = [0]*h
w_array = [0]*w

for hw in hw_array:
    h, w = hw
    h_array[h - 1] += 1
    w_array[w - 1] += 1

h_max = max(h_array)
h_argmax_array = [True if i == h_max else False for i in h_array]
w_max = max(w_array)
w_argmax_array = [True if j == w_max else False for j in w_array]

comb = sum(h_argmax_array) * sum(w_argmax_array)
for hw in hw_array:
    h, w = hw
    if h_argmax_array[h - 1] and w_argmax_array[w - 1]:
        comb -= 1
ans = h_max + w_max
if comb == 0:
    ans -= 1

print(ans)

Submission status: Accepted

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

hc = [0] * H
wc = [0] * W
d = {}
for _ in range(M):
    h, w = map(lambda x: int(x) - 1,input().split())
    hc[h] += 1
    wc[w] += 1
    d.setdefault(h, {})
    d[h][w] = 1

result = 0
hm = max(hc)
wm = max(wc)
hi = [i for i in range(H) if hc[i] == hm]
wi = [i for i in range(W) if wc[i] == wm]

for h in hi:
    for w in wi:
        if h in d and w in d[h]:
            result = max(result, hm + wm - 1)
        else:
            result = max(result, hm + wm)
            break
print(result)

Submission status: Accepted

Solution code:
#import numpy as np
import collections
#import math




#f = open('./input_E.txt')
#
#H,W,M=map(int, f.readline().split())
#bakuha = []
#bakuha_H=[]
#bakuha_W=[]
#for i in range(M):
#    hh,ww=map(int, f.readline().split())
#    bakuha_H.append(hh)
#    bakuha_W.append(ww)
#    bakuha.append([hh,ww])




H,W,M=map(int, input().split())
bakuha = []
bakuha_H=[]
bakuha_W=[]
for i in range(M):
    hh,ww=map(int, input().split())
    bakuha_H.append(hh)
    bakuha_W.append(ww)
    bakuha.append([hh,ww])





count_H = collections.Counter(bakuha_H)
H_most = count_H.most_common()
H_most_num = H_most[0][1]

#H_only_most = [x for x in H_most if x[1]==H_most_num]
#H_kouho = [x[0] for x in H_only_most]

H_kouho = [x[0] for x in H_most if x[1]==H_most_num]


count_W = collections.Counter(bakuha_W)
W_most = count_W.most_common()
W_most_num = W_most[0][1]

#W_only_most = [x for x in W_most if x[1]==W_most_num]
#W_kouho = [x[0] for x in W_only_most]
W_kouho = [x[0] for x in W_most if x[1]==W_most_num]

ans = H_most_num + W_most_num

#マイナス1するかどうか
ans_minus = True

len_H_kouho=len(H_kouho)
len_W_kouho=len(W_kouho)
num_kouho = len_H_kouho*len_W_kouho

bakuha_1d = [W * (x[0]-1) + x[1] for x in bakuha]
bakuha_1d.sort(reverse=True)
bakuha_1d_max = bakuha_1d[0]
bakuha_1d_min = bakuha_1d[-1]

#print(bakuha_1d)

if num_kouho <= M:
    kouho_1d = []
    for h_k in H_kouho:
        for w_k in W_kouho:
            kouho_1d.append(W*(h_k-1)+w_k)
    kouho_1d.sort()
    kouho_1d_min = kouho_1d[0]
    kouho_1d_max = kouho_1d[-1]
    
#    print(kouho_1d)    
    
    if kouho_1d_max <= bakuha_1d_max and kouho_1d_min >= bakuha_1d_min:
        b1_0 = bakuha_1d_min
        for_break=False
        for k1 in kouho_1d:
#            if k1 >= b1_0:
            tuzuku = True
            while tuzuku:
                b1_0 = bakuha_1d.pop()
#                print(k1,b1_0)
                if b1_0 >= k1:
                    tuzuku = False
                    if b1_0 != k1:
                        ans_minus = False
                        for_break=True
            if for_break:
                break
    else:
        ans_minus = False
#    for i in range(M):
#        b1_0 = bakuha_1d.pop(0)
        
        
        
else:
    ans_minus = False
#
#print(ans_minus)
if ans_minus:
    ans-=1
    

print(ans)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)] #bombの位置
a=[0 for i in range(h+1)] #各行のbombの個数
b=[0 for _ in range(w+1)] #各列のbombの個数
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a) #１行にあるbombの最大値
bm=max(b) #１列にあるbombの最大値
hmax=[0]*(h+1) #最大値をとるh全部
wmax=[0]*(w+1) #最大値をとるw全部
for i in range(h+1):
    if am==a[i]:
        hmax[i]+=1
for i in range(w+1):
    if bm==b[i]:
        wmax[i]+=1
ans=am+bm #基本解
k=sum(hmax)*sum(wmax)
if k>m: #鳩ノ巣原理
    print(ans)
    exit()
for i in bomb:
    if hmax[i[0]]==1 and wmax[i[1]]==1:
        k-=1
if k==0:
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product
H, W, M = map(int, input().split())
hsum = [0 for i in range(H)]
wsum = [0 for i in range(W)]
s = set()
for i in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    s.add((h, w))
    hsum[h] += 1
    wsum[w] += 1

hmax = max(hsum)
wmax = max(wsum)

hmax_index = []
for i in range(H):
    if hsum[i] == hmax:
        hmax_index.append(i)
wmax_index = []
for i in range(W):
    if wsum[i] == wmax:
        wmax_index.append(i)

for x in hmax_index:
    for y in wmax_index:
        if (x, y) not in s:
            print(hmax+wmax)
            sys.exit()
print(hmax+wmax-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

h = defaultdict(int)
w = defaultdict(int)
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    boms.add((x, y))

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

h_idx = [x for x, y in h.items() if y == h_max]
w_idx = [x for x, y in w.items() if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)

Submission status: Accepted

Solution code:
import sys

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

hw.sort()

hcnt = [0] * (H+1)
wcnt = [0] * (W+1)

target = []
for i, j in hw:
    hcnt[i] += 1
    wcnt[j] += 1
    target.append([str(i) + " " + str(j),1])

d = dict(target)

hlist = []
hmax = -1
for i in range(1,H+1):
    if hmax < hcnt[i]:
        hlist = [i]
        hmax = hcnt[i]
    elif hmax == hcnt[i]:
        hlist.append(i)

wlist = []
wmax = -1
for i in range(1,W+1):
    if wmax < wcnt[i]:
        wlist = [i]
        wmax = wcnt[i]
    elif wmax == wcnt[i]:
        wlist.append(i)

if len(hlist) * len(wlist) > M:
    print(hmax + wmax)
    sys.exit()

idx = 0
for h in hlist:
    for w in wlist:
        while h > hw[idx][0] or w > hw[idx][1]:
            idx += 1
            if idx == M:
                print(hmax + wmax)
                sys.exit()                
            if h == hw[idx][0] and w == hw[idx][1]:
                break
        if h < hw[idx][0] or w < hw[idx][1]:
            print(hmax + wmax)
            sys.exit()
        
print(hmax + wmax - 1)

Submission status: Accepted

Solution code:
import bisect
h,w,m=map(int,input().split())
hl=[0]*h
wl=[0]*w
s=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    hl[a]+=1
    wl[b]+=1
    s.append([a,b])
mh=max(hl)
mw=max(wl)
hh=[]
ww=[]
for i in range(h):
    if hl[i]==mh:
        hh.append(i)
for i in range(w):
    if wl[i]==mw:
        ww.append(i)
f=0
for a,b in s:
    hi=bisect.bisect_left(hh,a)
    wi=bisect.bisect_left(ww,b)
    if hi!=len(hh) and hh[hi]==a and wi!=len(ww) and ww[wi]==b:
        f+=1
if len(hh)*len(ww)>f:
    print(mh+mw)
else:
    print(mh+mw-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

nh = [0] * H  # number of h == i+1
nw = [0] * W  # number of w == i+1
dic = defaultdict(bool)

for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    nh[h[i]] += 1
    nw[w[i]] += 1
    dic["{}-{}".format(h[i],w[i])] = True

mnh = max(nh)
mnw = max(nw)

mh = [i for i, nh1 in enumerate(nh) if nh1 == mnh]
mw = [i for i, nw1 in enumerate(nw) if nw1 == mnw]

for h1 in mh:
    for w1 in mw:
        if not dic["{}-{}".format(h1,w1)]:
            print(mnh + mnw)
            exit()
print(mnh + mnw - 1)

Submission status: Accepted

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

h = [0] * H
w = [0] * W
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

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

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    s = set()
    h,w,m = map(int,input().split())
    a = [0]*h
    b = [0]*w
    for i in range(m):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        a[x] += 1
        b[y] += 1
        s.add((x,y))
    amax = max(a)
    bmax = max(b)
    c = []
    d = []
    for i in range(len(a)):
      if amax == a[i]:
        c.append(i)
    for i in range(len(b)):
      if bmax == b[i]:
        d.append(i)
    minus = True
    end = False
    for x in c:
      for y in d:
        if not (x,y) in s:
          minus = False
          end = True
        if end:
            break
      if end:
        break
    ans = amax+bmax
    if minus:
        ans -= 1
    print(ans)

Submission status: Accepted

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

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

    
ans = ch_max + cw_max
if len(ys) * len(xs) <= m:
    def _find():
        for x in xs:
            for y in ys:
                if (y, x) not in points:
                    return True
        return False
    if not _find():
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W, M = map(int, input().split())
h_cnt = [0] * H
w_cnt = [0] * W
s = set()
for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    h_cnt[h] += 1
    w_cnt[w] += 1
    s.add((h, w))

cand1 = max(h_cnt) + max(w_cnt)
cand2 = cand1 - 1

x = Counter(h_cnt)
y = Counter(w_cnt)

def check(k):
    cnt = False
    for i in range(k + 1):
        cnt += x[i] * y[k - i]
    for h, w in s:
        if h_cnt[h] + w_cnt[w] == k:
            cnt -= 1
        if h_cnt[h] + w_cnt[w] == k + 1:
            cnt += 1
    return cnt > 0

if check(cand1):
    print(cand1)
else:
    print(cand2)

Submission status: Accepted

Solution code:
def main():
    h, w, m = map(int, input().split())
    lsh = [0] * h
    lsw = [0] * w

    bom = set()
    for _ in range(m):
        m1, m2 = map(int, input().split())
        lsh[m1 - 1] += 1
        lsw[m2 - 1] += 1
        bom.add((m1-1, m2-1))

    lshmax = max(lsh)
    lswmax = max(lsw)

    hin = [i for i in range(h) if lsh[i] == lshmax]
    win = [i for i in range(w) if lsw[i] == lswmax]

    for i in hin:
        for j in win:
            if (i, j) not in bom:
                print(lshmax + lswmax)
                exit(0)
    else:
        print(lshmax + lswmax -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mp = set()
hp = [0] * h
wp = [0] * w

for i in range(m):
    a, b = map(int, input().split())
    mp.add((a, b))
    l = [a, b]
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1

maxhp = max(hp)
maxwp = max(wp)
hpdex = [i for i, x in enumerate(hp) if x == maxhp]
wpdex = [i for i, x in enumerate(wp) if x == maxwp]

for i in hpdex:
    for j in wpdex:
        if (i+1, j+1) not in mp:
            print(max(hp) + max(wp))
            exit()

print(max(hp) + max(wp) - 1)

Submission status: Accepted

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

# スペース区切りの整数の入力
h, w, m = map(int, input().split())

h_list = [0]*h
w_list = [0]*w

# h_w_list = [[0 for j in range(w)] for i in range(h)]
# h_w_list = []
h_w_list = set()

for zzz in range(m):
  # print("---")
  bom_h, bom_w = map(int, input().split())
  # print(bom_h, bom_w)
  h_list[bom_h-1] += 1
  w_list[bom_w-1] += 1

  # h_w_list[bom_h-1][bom_w-1] = 1
  # h_w_list.append([bom_h, bom_w])
  h_w_list.add((bom_h, bom_w))

mh = max(h_list)
mw = max(w_list)
h_max_indexs = [i for i, v in enumerate(h_list) if v == mh]
w_max_indexs = [i for i, v in enumerate(w_list) if v == mw]

double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    # chance = h_w_list.count([h_index + 1, w_index + 1]) == 0
    chance = (h_index + 1, w_index + 1) not in h_w_list

    if chance:
      double_chance = True


if double_chance:
  result = mh + mw
else:
  result = mh + mw -1

print(result)

Submission status: Accepted

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

column_cnt = [0]*W
row_cnt = [0]*H

for bomb_pos in bomb:
    row_cnt[bomb_pos[0]-1] += 1
    column_cnt[bomb_pos[1]-1] += 1

row_max_index = row_cnt.index(max(row_cnt))
column_max_index = column_cnt.index(max(column_cnt))

bomb_cnt_max = 0

for bomb_pos in bomb:
    bomb_cnt = row_cnt[bomb_pos[0]-1] + column_cnt[column_max_index]
    if (bomb_pos[0], column_max_index+1) in bomb:
        bomb_cnt -= 1
    bomb_cnt_max = max(bomb_cnt_max, bomb_cnt)

    bomb_cnt = column_cnt[bomb_pos[1]-1] + row_cnt[row_max_index]
    if (row_max_index+1, bomb_pos[1]) in bomb:
        bomb_cnt -= 1
    bomb_cnt_max = max(bomb_cnt_max, bomb_cnt)

print(bomb_cnt_max)

Submission status: Accepted

Solution code:
h,w,m= map(int,input().split(" "))
ys, xs=[0 for i in range(h)],[0 for j in range(w)]
ms=set()
for i in range(m):
    y,x= map(lambda x: int(x)-1,input().split(" "))
    ys[y]+=1
    xs[x]+=1
    ms.add((y,x))
y_max,x_max= max(ys),max(xs)
largest_ys, largest_xs=[],[]
for i in range(h):
    if ys[i]==y_max:
        largest_ys.append(i)
for i in range(w):
    if xs[i]==x_max:
        largest_xs.append(i)
ans=y_max+x_max-1
for i in largest_ys:
    for j in largest_xs:
        if (i,j) not in ms:
            print(ans+1)
            exit()
print(ans)