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

h, w, m = map(int, input().split())
G = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
A = [0]*h
B = [0]*w
for i, j in G:
  A[i] += 1
  B[j] += 1
ans = 0
max_A = max(A)
max_B = max(B)
cnt = A.count(max_A) * B.count(max_B)
for i, j in G:
  if A[i] == max_A and B[j] == max_B:
    cnt -= 1
if cnt == 0:
  print(max_A+max_B-1)
else:
  print(max_A+max_B)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
L=[0 for _ in range(H)]
C=[0 for _ in range(W)]
B={}
for _ in range(M):
    a,b=map(int,input().split())
    B[str(a)+","+str(b)]=0
    L[a-1]+=1
    C[b-1]+=1

LM=max(L)
CM=max(C)

l=[]
c=[]
for j in range(H):
    if L[j]==LM:
        l.append(j)

for k in range(W):
    if C[k]==CM:
        c.append(k)

ans=LM+CM-1

for a in l:
    for b in c:
        if str(a+1)+","+str(b+1) not in B:
            ans=LM+CM
            break
    if ans==LM+CM:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
b=[]
for i in range(m):
    hi,wi=map(int,input().split())
    b.append((hi-1,wi-1))

H=[0]*h
W=[0]*w
for i in b:
    H[i[0]]+=1
    W[i[1]]+=1

hm=set()
wm=set()

hM=max(H)
for i in range(h):
    if H[i]==hM:
        hm.add(i)
wM=max(W)
for i in range(w):
    if W[i]==wM:
        wm.add(i)

count=0
for i in b:
    if i[0] in hm and i[1] in wm:
        count+=1

if len(hm)*len(wm)<=count:
    print(hM+wM-1)
else:
    print(hM+wM)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np

if __name__ == '__main__':
    H, W, M = list(map(lambda x: int(x), sys.stdin.readline().split()))

    dic = {}
    # h = [0 for i in range(H)]
    # w = [0 for i in range(W)]
    h = np.zeros(H, dtype=np.int64)
    w = np.zeros(W, dtype=np.int64)
    for i in range(M):
        # P.append(list(map(lambda x: int(x), sys.stdin.readline().split())))
        x, y = list(map(lambda x: int(x), sys.stdin.readline().split()))
        x -= 1
        y -= 1
        h[x] += 1
        w[y] += 1
        dic[x*H+y] = 1
    
    lh = np.where(h == h.max())
    lw = np.where(w == w.max())

    mx = np.max(h)
    my = np.max(w)
    # print(mx, my)

    # print(lh[0])
    # print(lw[0])


    tmp = mx + my
    for i in lh[0]:
        for j in lw[0]:
            if i*H+j not in dic:
                print(tmp)
                exit()
    print(tmp-1)
    exit()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial,sqrt
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    h,w,m=MI()
    lis1=[]
    lis2=[]
    for i in range(m):
        a,b=MI()
        lis1.append(a)
        lis2.append(b)
    c1=Counter(lis1)
    X=c1.most_common()
    #print(c1)
    c2=Counter(lis2)
    Y=c2.most_common()
    #print(c2)
    cand1=[]
    cand2=[]
    s=X[0][1]
    for a,b in X:
        if b==s:
            cand1.append(a)
        else:
            break
    #print(cand1)
    t=Y[0][1]
    for a,b in Y:
        if b==t:
            
            cand2.append(a)
        else:
            break
    #print(cand2)
    cand1.sort()
    cand2.sort()
    rest=len(cand1)*len(cand2)
    for i in range(m):
        x,y=lis1[i],lis2[i]
        if cand1[bisect_right(cand1,x)-1]==x and cand2[bisect_right(cand2,y)-1]==y:
            rest-=1
    if rest>0:
        print(s+t)
    else:
        print(s+t-1)
    
            
    

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())

    xy = [list(map(int, readline().split())) for i in range(M)]

    xs = {}
    ys = {}
    #debug = [['.'] * W for i in range(H)]
    for x,y in xy:
        if x not in xs:
            xs[x] = []
        xs[x].append((x, y))

        if y not in ys:
            ys[y] = []
        ys[y].append((x ,y))

        #debug[x-1][y-1] = '#'
    
    #pprint(debug)
    
    max_len_xs = max(len(v) for v in xs.values())
    max_len_ys = max(len(v) for v in ys.values())

    xs = {k: v for k,v in xs.items() if len(v) == max_len_xs}
    ys = {k: v for k,v in ys.items() if len(v) == max_len_ys}


    cy = {k: sum(1 if x in xs else 0 for x,y in v)
        for k,v in ys.items()}

    nn = len(xs)
    if all(v == nn for v in cy.values()):
        print(max_len_xs + max_len_ys - 1)
    else:
        print(max_len_xs + max_len_ys)
    

    #for v in xs.values():
    #    for x,y in v:
    #        if y in cy:
    #            cy[y] -= 1
    
    
    #print(cy)
    #if all(c == 0 for c in cy.values()):
    #    print(max_len_xs + max_len_ys - 1)
    #else:
    #    print(max_len_xs + max_len_ys)

solve()

Submission status: Accepted

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

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

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

x_score = [0]*300009
y_score = [0]*300009

elems = set()

for _ in range(M):
    h, w = input().split()
    h = int(h)
    w = int(w)

    x_score[h] += 1
    y_score[w] += 1

    elems.add((h, w))

best_x_score = max(x_score)
best_y_score = max(y_score)

best_x = []
best_y = []

for i in range(len(x_score)):
    if x_score[i] == best_x_score:
        best_x += [i]
    
for i in range(len(y_score)):
    if y_score[i] == best_y_score:
        best_y += [i]

import sys

if len(best_x)*len(best_y) > M+10:
    print(best_x_score + best_y_score)
    sys.exit(0)

for x in best_x:
    for y in best_y:
        if (x, y) not in elems:
            print(best_x_score + best_y_score)
            sys.exit(0)

print(best_x_score + best_y_score - 1)

Submission status: Accepted

Solution code:
import random
import time

t0 = time.time()

H, W, M = map(int, input().split())
count_h = [0] * H
count_w = [0] * W
bomb = set()
for _ in range(M):
    h, w = map(int, input().split())
    bomb.add((h-1, w-1))
    count_h[h-1] += 1
    count_w[w-1] += 1

max_count_h = max(count_h)
max_count_w = max(count_w)

hs = [h for h in range(H) if count_h[h] == max_count_h]
ws = [w for w in range(W) if count_w[w] == max_count_w]

# H, W, M, bomb, count_h, count_w, hs, ws

ans = max_count_h + max_count_w

# t0 = time.time()
flag = False
while time.time() - t0 < 2.8:
    h = random.choice(hs)
    w = random.choice(ws)
    if (h, w) not in bomb:
#         print(h, w)
        flag = True
        break
if flag:
    print(ans)
else:
    print(ans - 1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,M = MI()
hw = [tuple(MI()) for _ in range(M)]
A = [0]*(H+1)
B = [0]*(W+1)

from collections import defaultdict
d = defaultdict(int)
for h,w in hw:
    A[h] += 1
    B[w] += 1
    d[(h,w)] = 1


ma = max(A)
mb = max(B)
ans = ma+mb
C,D = [],[]
for i in range(1,H+1):
    if A[i] == ma:
        C.append(i)
for i in range(1,W+1):
    if B[i] == mb:
        D.append(i)

if len(C)*len(D) > M:
    print(ans)
else:
    for i in C:
        for j in D:
            if d[(i,j)] == 0:
                print(ans)
                exit()
    print(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]]

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])

Submission status: Accepted

Solution code:
from collections import Counter
n,m,targets = map(int,input().split())
r,c = {},{}
rcnt,ccnt = Counter(),Counter()
done = set()
for _ in range(targets):
    i,j = map(int,input().split())
    done.add((i,j))
    rcnt[i] += 1
    ccnt[j] += 1
    if i in r:
        r[i].append(j)
    else:
        r[i] = [j]
    if j in c:c[j]+=1
    else:c[j]=1
#print(r,c)
rs,cs = [],[]
mx1 = max([len(r[k]) for k in r.keys()])
mx2 = max(c.values())
ans = mx1 + mx2 - 1
for k in r.keys():
    if len(r[k])==mx1:
        rs.append(k)
for k in c.keys():
    if c[k] == mx2:
        cs.append(k)
#print(mx1,mx2)
#print(rs,cs)
flag = False
for row in rs:
    for col in cs:
        if (row,col) not in done:
            flag = True
            ans += 1
            break
    if flag:
        break
print(ans)


# for key in r.keys():
#     arr = r[key]
#     l = len(arr)
#     for v in arr:
#         cand = l + c[v] - 1
#         mx = max(cand,mx)
# rcnt = [(k,v) for (k,v) in rcnt.items()]
# ccnt = [(k,v) for (k,v) in ccnt.items()]

# rcnt.sort(key = lambda x:x[1],reverse = True)
# ccnt.sort(key = lambda x:x[1],reverse = True)
# rcnt = rcnt[:500]
# ccnt = ccnt[:500]
# #print(rcnt,ccnt)
# #print(done)
# for row in rcnt:
#     for col in ccnt:
#         rowk,colk = row[0],col[0]
#         if rowk in r and colk in c and (rowk,colk) not in done:
#             cand = len(r[rowk]) + c[colk]
#

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]

for j,k in l:
    count_h[j-1] += 1
    count_w[k-1] += 1

h_max = max(count_h)
w_max = max(count_w)
h_kouho = []
ko_hh = [0 for _ in range(h)]
ko_ww = [0 for _ in range(w)]
w_kouho = []
ans = h_max + w_max -1
for i in range(h):
    if count_h[i]==h_max:
        h_kouho.append(i)
        ko_hh[i] = 1
for j in range(w):
    if count_w[j]==w_max:
        w_kouho.append(j)
        ko_ww[j] = 1


ans_kouho = len(h_kouho) * len(w_kouho)
su = 0
for j,k in l:
    if ko_hh[j-1]==1 and ko_ww[k-1]==1:
        su += 1
if su==ans_kouho:
    print(ans)
else:
    print(ans+1)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, M = [int(x) for x in input().split()]
    HW = [[int(x) for x in input().split()] for _ in range(M)]

    x = set()

    hc = collections.Counter()
    wc = collections.Counter()

    for h, w in HW:
        hc[h] += 1
        wc[w] += 1
        x.add((h, w))

    ans = 0
    hcma = hc.most_common()[0][1]
    wcma = wc.most_common()[0][1]
    f = False
    bost_common = wc.most_common()
    for a in hc.most_common():
        if a[1] != hcma:
            break
        for b in bost_common:
            if b[1] != wcma:
                break
            if (a[0], b[0]) in x:
                ans = max(ans, hcma + wcma - 1)
            else:
                ans = max(ans, hcma + wcma)
                f = True
                break
        if f:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

@njit((i8, i8, i8[:]), cache=True)
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] - 1
        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] - 1
        if row[x] == row_max and col[y] == col_max:
            choice -= 1
    x = row_max + col_max
    return x if choice else x - 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:
import sys
from collections import Counter
from random import shuffle
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = []
w_targets = []

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets.append(h)
    w_targets.append(w)

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_high = h_counter[0][1]
w_high = w_counter[0][1]

h_counter = [[k, v] for k, v in h_counter if v == h_high]
w_counter = [[k, v] for k, v in w_counter if v == w_high]
shuffle(h_counter)
shuffle(w_counter)

highest = h_high + w_high
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        if ((hk, wk) not in targets):
            print(highest)
            exit()
print(highest - 1)

Submission status: Accepted

Solution code:
from collections import Counter

def main(H, W, M, obj_h, obj_w, obj):
    c_h = Counter(obj_h)
    c_w = Counter(obj_w)
    max_h = max(c_h.values())
    max_w = max(c_w.values())
    lst_h = [kv[0] for kv in c_h.items() if kv[1] == max_h]
    lst_w = [kv[0] for kv in c_w.items() if kv[1] == max_w]
    for h in lst_h:
        for w in lst_w:
            if (h, w) not in obj:
                print(max_h + max_w)
                exit()
    else:
        print(max_h + max_w - 1)



if __name__ == '__main__':
    H, W, M = list(map(int, input().split()))
    obj = set()
    obj_h = []
    obj_w = []
    for _ in range(M):
        i = list(map(int, input().split()))
        obj.add(tuple(i))
        obj_h.append(i[0])
        obj_w.append(i[1])
    main(H, W, M, obj_h, obj_w, obj)

Submission status: Accepted

Solution code:
H,W, M = map(int, input().split())
HW = [[int(i) - 1 for i in input().split()] for _ in range(M)]

from collections import defaultdict

S = defaultdict(bool)
Hcnt = [0] * H
Wcnt = [0] * W
for h, w in HW:
    S[(h, w)] = True
    Hcnt[h] += 1
    Wcnt[w] += 1

# Hを先に決めるver
ans = 0
Hmax = max(Hcnt)
Wmax= max(Wcnt)
Hidx = []
Widx = []
for i,h in enumerate(Hcnt):
    if Hmax == h:
        Hidx.append(i)
for j,w in enumerate(Wcnt):
    if Wmax == w:
        Widx.append(j)

for i in Hidx:
    for j in Widx:
        if S[(i, j)]:
            ans = Hmax + Wmax - 1
        else:
            ans = Hmax + Wmax
            print(ans)
            exit()

print(ans)

Submission status: Accepted

Solution code:
import itertools

int1 = lambda x: int(x) - 1

H, W, M = map(int, input().split())
rows, columns = [0] * H, [0] * W
Bomb = set()
for _ in range(M):
    h, w = map(int1, input().split())
    rows[h] += 1
    columns[w] += 1
    Bomb.add((h, w))

r_first = []
r_max = max(rows)
for i, x in enumerate(rows):
    if x == r_max:
        r_first.append(i)

c_first = []
c_max = max(columns)
for i, x in enumerate(columns):
    if x == c_max:
        c_first.append(i)

ans = 0
for i, j in itertools.product(r_first, c_first):
    if (i, j) in Bomb:
        ans = r_max + c_max - 1
    else:
        ans = r_max + c_max
        break
print(ans)

Submission status: Accepted

Solution code:
H, W, M = list(map(int, input().split()))
h = [0] * H
w = [0] * W
s = set()
for i in range(M):
    x, y = list(map(int, input().split()))
    h[x - 1] += 1
    w[y - 1] += 1
    s.add((x-1, y-1))
hmax = max(h)
wmax = max(w)
hidx = []
for i, e in enumerate(h):
    if e == hmax:
        hidx.append(i)
widx = []
for i, e in enumerate(w):
    if e == wmax:
        widx.append(i)
l_flag = False
for i in hidx:
    for j in widx:
        if (i, j) not in s:
            l_flag = True
            break
    if l_flag:
        break
if l_flag:
    ans = hmax + wmax
else:
    ans = hmax + wmax - 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():

    H, W, M = map(int, input().split())
    #HW = [0]*m

    HC = [0]*H
    WC = [0]*W

    A = [0]*M

    for i in range(M):
        h, w = map(int, input().split())
        h, w = h-1, w-1
        #HW[i] = (h, w)
        HC[h] += 1
        WC[w] += 1
        A[i] = (h, w)

    from collections import Counter
    hct = Counter(HC)
    wct = Counter(WC)
    hct = list(hct.items())
    wct = list(wct.items())
    hct.sort(reverse=True)
    wct.sort(reverse=True)
    #print(hct)
    #print(wct)
    temph = hct[0][0]
    tempw= wct[0][0]
    tempa = temph+tempw
    cnthw = hct[0][1]*wct[0][1]
    cnt = 0
    for h, w in A:
        if HC[h]+WC[w] ==tempa:
            cnt += 1
    #print(cnt, cnthw)
    if cnt < cnthw:
        print(tempa)
    else:
        print(tempa-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, M = (int(i) for i in input().split())

hw = set()
hh = [0] * H
ww = [0] * W

for i in range(M):
    ht , wt = (int(i) for i in input().split())
    hw.add((ht-1) * W + wt - 1)
    hh[ht-1] += 1
    ww[wt-1] += 1

hhh = max(hh)
ih = [i for i, x in enumerate(hh) if x == hhh]

www = max(ww)
iw = [i for i, x in enumerate(ww) if x == www]

minus = 1
for iih in ih:
    for iiw in iw:
        if iih * W + iiw not in hw:
            minus = 0
            break

print(hhh + www - minus)

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:
import sys
input = sys.stdin.readline
h, w, m = map(int, input().split())
a = [0] * h
b = [0] * w
H, W = [0] * m, [0] * m
for i in range(m):
    H[i], W[i] = map(int, input().split())
    H[i] -= 1
    W[i] -= 1
    a[H[i]] += 1
    b[W[i]] += 1
a1 = max(a)
a2 = max(b)
s = sum(i == a1 for i in a)
t = sum(i == a2 for i in b)
ans = 0
for i in range(m):
    if a[H[i]] == a1 and b[W[i]] == a2:
        ans += 1
print(a1 + a2 - 1 if ans == s * t else a1 + a2)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
height=[0]*H
width=[0]*W
#bomb=[0]*M
bset=set()
#for k in range(M):
    #bomb[k]=[0]*2
for j in range(M):
    h,w=map(int,input().split())
    bset.add((h-1,w-1))
    #bomb[j][0]=h-1
    #bomb[j][1]=w-1
    height[h-1]+=1
    width[w-1]+=1
#print(bomb)
#print(height)
#print(width)
hmax=max(height)
wmax=max(width)
hindex=0
windex=0
for i in range(H):
    if height[i]==hmax:
        #print(i)
        hindex+=1
for h in range(W):
    if width[h]==wmax:
        #print(h)
        windex+=1
kouho=hindex*windex
equalbomb=0
for p in bset:
    if height[p[0]]==hmax and width[p[1]]==wmax:
        #print(p)
        equalbomb+=1

if kouho==equalbomb:
    print(hmax+wmax-1)
else:
    print(hmax+wmax)

Submission status: Accepted

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
hl=[]
wl=[]
hwl=set()
for _ in range(M):
    h,w=map(int,input().split())
    hl.append(h)
    wl.append(w)
    hwl.add((h,w))
hl=Counter(hl).most_common()
wl=Counter(wl).most_common()
hm=hl[0][1]
wm=wl[0][1]
for h,hc in hl:
    if hc<hm:
        break
    for w,wc in wl:
        if wc<wm:
            break
        if (h,w) not in hwl:
            print(hm+wm)
            exit()
print(hm+wm-1)

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
h = [0] * (H+1)
w = [0] * (W+1)
hw = []
for i in range(M):
    hin,win = map(int,input().split())
    hw.append((hin,win))
    h[hin] += 1
    w[win] += 1
maxh = max(h)
maxw = max(w)
hlis = set()
for i in range(H+1):
    if h[i] == maxh:
        hlis.add(i)
wlis = set()
for i in range(W+1):
    if w[i] == maxw:
        wlis.add(i)
#print(hlis,wlis)
cnt = 0
for i in hw:
    if i[0] in hlis and i[1] in wlis:
        cnt += 1
if cnt == len(hlis) * len(wlis):
    print(maxh+maxw-1)
else:
    print(maxh+maxw)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W, M, *T = map(int, read().split())

    counter = Counter()
    counter_h = [0] * H
    counter_w = [0] * W
    for h, w in zip(*[iter(T)] * 2):
        counter[(h - 1, w - 1)] += 1
        counter_h[h - 1] += 1
        counter_w[w - 1] += 1

    max_h = max(counter_h)
    max_w = max(counter_w)
    max_h_index = [False] * H
    max_w_index = [False] * W
    for i in range(H):
        if counter_h[i] == max_h:
            max_h_index[i] = True
    for j in range(W):
        if counter_w[j] == max_w:
            max_w_index[j] = True

    n = 0
    for h, w in zip(*[iter(T)] * 2):
        h -= 1
        w -= 1
        if max_h_index[h] and max_w_index[w]:
            n += 1

    if n == sum(max_h_index) * sum(max_w_index):
        ans = max_h + max_w - 1
    else:
        ans = max_h + max_w

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
H,W,M = ma()
hw = []
coh = collections.Counter()
cow = collections.Counter()
se=set()
for i in range(M):
    h,w = ma()
    coh[h]+=1
    cow[w] +=1
    se.add((h,w))

lh =  list(coh.items())
lw =  list(cow.items())
#print(lh,lw)
lh.sort(key=lambda x:x[1],reverse=True)
lw.sort(key=lambda x:x[1],reverse=True)
mah = lh[0][1]
maw = lw[0][1]
lhh = [num for num,cnt in lh if cnt==mah]
lww = [num for num,cnt in lw if cnt==maw]
ans = mah+maw

f=False
if len(lhh)*len(lww)<=M:
    for h in lhh:
        for w in lww:
            if not (h,w) in se:
                f=True
    if f:
        print(ans)
    else:
        print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,M=MI()
    nh=[0]*H
    nw=[0]*W
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(M):
        h,w=MI()
        h-=1
        w-=1
        dd[(h,w)]=1
        nh[h]+=1
        nw[w]+=1
        
    Mh=max(nh)
    Mw=max(nw)
    
    if Mh==0:
        print(Mw)
    elif Mw==0:
        print(Mh)
    else:
        ans=Mh+Mw-1#交差するところに爆弾があったと仮定する．なければあとで+1
        
        hh=[]
        ww=[]
        for i in range(H):
            if nh[i]==Mh:
                hh.append(i)
        
        for i in range(W):
            if nw[i]==Mw:
                ww.append(i)
                
        for h in hh:
            for w in ww:
                if dd[(h,w)]==0:
                    ans+=1
                    print(ans)
                    exit()
        print(ans)
                

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MAX = 3*10**5+1

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

A = [set() for _ in range(MAX)]
B = [set() for _ in range(MAX)]
for _ in range(M):
    h, w = map(int, input().split())
    A[h].add(w)
    B[w].add(h)

B.sort(key=lambda x : len(x), reverse=True)
L = len(B[0])
P = []
for b in B:
    if len(b) == L:
        P.append(b)

ans = 0
for h in range(MAX):
    score = len(A[h]) + L - 1
    for p in P:
        if not h in p:
            score += 1
            break
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
from itertools import product
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def solve(bombs,H,W):

    X = [0]*H
    Y = [0]*W

    for x,y in bombs:
        X[x] += 1
        Y[y] += 1

    mx = max(X)
    my = max(Y)

    x_ind = [i for i,c in enumerate(X) if c==mx]
    y_ind = [i for i,c in enumerate(Y) if c==my]

    if len(x_ind)*len(y_ind) > len(bombs):
        return mx+my

    bombs = set(bombs)
    candidates = set(product(x_ind,y_ind))

    return mx+my-1 if bombs >= candidates else mx+my


if __name__ == '__main__':
    H,W,M = map(int,readline().split())

    t = map(lambda x: int(x)-1, read().split())

    bombs = list(zip(t,t))

    print(solve(bombs,H,W))

Submission status: Accepted

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

bomb=set([])

zahyo_y=[0]*(h)
zahyo_x=[0]*(w)

#print(zahyo_y)
#print(zahyo_x)

maxy=0
maxy_index=[]
maxx=0
maxx_index=[]

for _ in range(m):
    y,x=map(int,input().split())
    bomb.add((y-1,x-1))
    zahyo_y[y-1]+=1
    zahyo_x[x-1]+=1

    if zahyo_y[y-1]==maxy:
        maxy_index.append(y-1)
    elif zahyo_y[y-1]>maxy:
        maxy_index=[y-1]
        maxy=zahyo_y[y-1]

    if zahyo_x[x-1]==maxx:
        maxx_index.append(x-1)
    elif zahyo_x[x-1]>maxx:
        maxx_index=[x-1]
        maxx=zahyo_x[x-1]

for x in maxx_index:
    for y in maxy_index:
        if (y,x) not in bomb:
            print(maxx+maxy)
            exit()

print(maxx+maxy-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
col = [0] * w
row = [0] * h
places = set()
for _ in range(m):
    h, w = map(int, input().split())
    h -= 1; w -= 1
    row[h] += 1
    col[w] += 1
    places.add((h, w))

col_wi = []
for i, item in enumerate(col):
    col_wi.append((item, i))
row_wi = []
for i, item in enumerate(row):
    row_wi.append((item, i))

col_wi.sort(reverse=True)
row_wi.sort(reverse=True)

col_max = col_wi[0][0]
row_max = row_wi[0][0]

ans = 0
has_blank_center = False
for cval, ci in col_wi:
    if cval != col_max:
        break
    for rval, ri in row_wi:
        if rval != row_max:
            break
        if (ri, ci) not in places:
            has_blank_center = True
            break
    if has_blank_center:
        break

if has_blank_center:
    print(col_max + row_max)
else:
    print(col_max + row_max - 1)

Submission status: Accepted

Solution code:
hwm=input("").split(" ")
h=int(hwm[0])
w=int(hwm[1])
m=int(hwm[2])
liw=[]
ww=[]
hh=[]
for i in range(w):
    liw+=[[]]
    ww+=[0]
for i in range(h):
    hh+=[0]
for i in range(m):
    hw=input("").split(" ")
    hh[int(hw[0])-1]+=1
    ww[int(hw[1])-1]+=1
    liw[int(hw[1])-1]+=[int(hw[0])-1]
mw=max(ww)
mh=max(hh)
w0=[]

h0=[]

c=0
for i in ww:
    if(mw==i):
        w0+=[c]
    
    c+=1
c=0
for i in hh:
    if(mh==i):
        h0+=[c]
    
    c+=1
for i in w0:
    if not(set(h0)<=set(liw[i])):
        print(mh+mw)
        break
else:
    print(mh+mw-1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort()
a={}
b={}
for i in l:
    if i[0] in a:
        a[i[0]]+=1
    else:
        a[i[0]]=1
    if i[1] in b:
        b[i[1]]+=1
    else:
        b[i[1]]=1
ma=max(list(b.values()))
c={}
for i in b:
    if b[i]==ma:
        c[i]=1
ans=0
i=0
for j in a:
    e=0
    while i<m and l[i][0]==j:
        if l[i][1] in c:
            e+=1
        i+=1
    tans=a[j]+ma
    if e==len(c):
        tans-=1
    ans=max(ans,tans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, m = map(int, input().split())
    H_list = [0] * H
    W_list = [0] * W
    bomb = []
    for _ in range(m):
        h_, w_ = map(lambda x: int(x) - 1, input().split())
        H_list[h_] += 1
        W_list[w_] += 1
        bomb.append([h_, w_])

    ma = max(H_list) + max(W_list)
    cnt_H = Counter(H_list)
    cnt_W = Counter(W_list)
    cnt = 0
    for k, v in cnt_H.items():
        if cnt_W.get(ma - k) is not None:
            cnt += v * cnt_W[ma - k]

    for h, w in bomb:
        total = H_list[h] + W_list[w]
        if total == ma:
            cnt -= 1
    if cnt:
        print(ma)
    else:
        print(ma - 1)


if __name__ == '__main__':
    resolve()