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 random import randint
import numpy as np
from numba import njit


#@njit
def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Accepted

Solution code:
h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    M.add((mh-1, mw-1))
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)

Submission status: Accepted

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

for i in range(m):
  H,W=list(map(int,input().split()))
  s.append(H)
  t.append(W)
  
from collections import Counter
u=Counter(s)
v=Counter(t)
max_u=max(u.values())
max_u_set = set([kv[0] for kv in u.items() if kv[1]==max_u])
max_v=max(v.values())
max_v_set = set([kv[0] for kv in v.items() if kv[1]==max_v])
check=len(max_u_set)*len(max_v_set)

ans=0
for i in range(m):
  if u[s[i]]==max_u and v[t[i]]==max_v:
    ans=ans+1

if check-ans==0:
  print(max_u+max_v-1)
else:
  print(max_u+max_v)

Submission status: Accepted

Solution code:
h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)

Submission status: Accepted

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

bomb_and_max=0
for i,j in bomb:
    if h[i]==max_h and w[j]==max_w:
        bomb_and_max+=1
    
if bomb_and_max==h.count(max_h)*w.count(max_w):
    print(max_h+max_w-1)
else:
    print(max_h+max_w)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    row_dict = defaultdict(int)
    col_dict = defaultdict(int)
    row_col_dict = defaultdict(set)
    for _ in range(m):
        row, col = map(int, input().split())
        row_dict[row] += 1
        col_dict[col] += 1
        row_col_dict[row].add(col)

    max_row_val = max(row_dict.values())
    max_col_val = max(col_dict.values())

    max_rows = {k for k, v in row_dict.items() if v == max_row_val}
    max_cols = {k for k, v in col_dict.items() if v == max_col_val}
    ans = max_row_val + max_col_val - 1
    flg = False
    if ans < m:
        for row in max_rows:
            for col in max_cols:
                if not col in row_col_dict[row]:
                    ans += 1
                    flg = True
                    break
            if flg:
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for i in range(m)]
hb = [0] * h
wb = [0] * w

for i in range(m):
    hb[hw[i][0]-1] += 1
    wb[hw[i][1]-1] += 1

max_h = max(hb)
max_w = max(wb)
ans = max_h + max_w
count = hb.count(max_h) * wb.count(max_w)
for i in range(m):
    if hb[hw[i][0]-1] == max_h and wb[hw[i][1]-1] == max_w:
        count -= 1
if count <= 0:
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, m = map(int, input().split())
    hp = [0]*h
    wp = [0]*w
    hw = set()
    for _ in range(m):
        h1, w1 = map(int, input().split())
        hp[h1-1] += 1
        wp[w1-1] += 1
        hw.add((h1, w1))

    h_max = max(hp)
    w_max = max(wp)

    hh = [i+1 for i, v in enumerate(hp) if v == h_max]
    ww = [i+1 for i, v in enumerate(wp) if v == w_max]
    ans = h_max + w_max

    for hb in hh:
        for wb in ww:
            if (hb, wb) not in hw:
                print(ans)
                exit()
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find():
    h,w,m=map(int,input().split())
    idx=[]


    for i in range(m):
      var=list(map(int,input().split()))
      idx.append(var)


    r={}
    c={}
    #maze=[[0 for j in range(w)]for i in range(h)]
    mz={}

    for i in idx:
      mz.setdefault((i[0]-1,i[1]-1),0)
      mz[(i[0]-1,i[1]-1)]=1
      #maze[i[0]-1][i[1]-1]=1
      r.setdefault(i[0]-1,0)
      r[i[0]-1]+=1
      c.setdefault(i[1]-1,0)
      c[i[1]-1]+=1

    ans=0
    maxval=0



    row=[]
    col=[]
    maxr=max(r.values())
    maxc=max(c.values())
    for i in range(h):
      r.setdefault(i,0)
      if r[i]==maxr:
        row.append(i)
      

    for j in range(w):
      c.setdefault(j,0)
      if c[j]==maxc:
        col.append(j)
    
    for i in row:
      for j in col:
        mz.setdefault((i,j),0)
        if(mz[(i,j)]==0):
          return maxc+maxr
         
    return maxc+maxr-1
 
print(find())

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
row=[0 for i in range(h)]
col=[0 for i in range(w)]
a=[]
for i in range(m):
    r,c=map(lambda x:int(x)-1,input().split())
    a.append([r,c])
    row[r]+=1
    col[c]+=1
rmax=max(row)
cmax=max(col)
ans=rmax+cmax
flag=row.count(rmax)*col.count(cmax)
for i,j in a:
    if(row[i]==rmax and col[j]==cmax):
        flag-=1
if(flag==0):
    ans-=1
print(ans)

Submission status: Accepted

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

h, w = [0]*M, [0]*M
dic = set()
for i in range(M):
    h[i], w[i] = map(int, input().split())
    dic.add((h[i],w[i]))

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

for i in mode_h:
    for j in mode_w:
        if (i,j) not in dic:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)

Submission status: Accepted

Solution code:
import collections
import copy

a = list(map(int,input().split()))
c = []
d = []
for i in range(a[2]):
    b = list(map(int,input().split()))
    c.append(b[0])
    d.append(b[1])

ans1 = 0
ans2 = 0

cp = copy.copy(c)
dp = copy.copy(d)

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]
ans1 += gc
ans2 += hc
for i in range(a[2]):
    if cp[i] == g:
        d[i] = -1
    if dp[i] == h:
        c[i] = -1
e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

if g == -1:
    if gc == a[2]:
        gc = 0
    else:
        g = e.most_common()[1][0]
        gc = e.most_common()[1][1]
if h == -1:
    if hc == a[2]:
        hc = 0
    else:
        h = f.most_common()[1][0]
        hc = f.most_common()[1][1]

ans1 += hc
ans2 += gc
if ans1 > ans2:
    print(str(ans1))
else:
    print(str(ans2))

Submission status: Accepted

Solution code:
import collections, itertools

h, w, m = map(int, input().split())
bombs = set(tuple(map(int, input().split())) for _ in range(m))

a = collections.Counter(x for x, y in bombs)
b = collections.Counter(y for x, y in bombs)
a_max_val = max(a.values())
b_max_val = max(b.values())
a_max_list = [k for k, v in a.items() if v == a_max_val]
b_max_list = [k for k, v in b.items() if v == b_max_val]

for a_max, b_max in itertools.product(a_max_list, b_max_list):
    if not (a_max, b_max) in bombs:
        print(a_max_val + b_max_val)
        exit(0)

print(a_max_val + b_max_val - 1)

Submission status: Accepted

Solution code:
N=300005
n,m,nums=map(int,input().split())
x=[0 for i in range(nums)]
y=[0 for i in range(nums)]
rows=[0 for i in range(N)]
cols=[0 for i in range(N)]
for i in range(nums):
    xx,yy=map(int,input().split())
    x[i]=xx
    y[i]=yy
    rows[xx]+=1
    cols[yy]+=1
cnt_row=0
cnt_col=0
max_row=0
max_col=0
for i in range(N):
    if(rows[i]>max_row):
        max_row=rows[i]
        cnt_row=0
    if(rows[i]==max_row):
        cnt_row+=1
for i in range(N):
    if(cols[i]>max_col):
        max_col=cols[i]
        cnt_col=0
    if(cols[i]==max_col):
        cnt_col+=1
ans=max_row+max_col
cnt=0
for i in range(nums):
    if(rows[x[i]]==max_row and cols[y[i]]==max_col):
        cnt+=1
if(cnt==cnt_row*cnt_col):
    ans-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())
bombs = []
rows = [[]for _ in range(H)]
cols = [[]for _ in range(W)]
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    bombs.append((h, w))
    rows[h].append(w)
    cols[w].append(h)

max_row = 0
row_idx = set()
for i, row in enumerate(rows):
    if max_row < len(row):
        max_row = len(row)
        row_idx = {i}
        continue
    elif max_row == len(row):
        row_idx.add(i)

max_col = 0
col_idx = set()
for i, col in enumerate(cols):
    if max_col < len(col):
        max_col = len(col)
        col_idx = {i}
        continue
    elif max_col == len(col):
        col_idx.add(i)

ans = max_row+max_col
points = len(row_idx)*len(col_idx)
if M < points:
    print(ans)
else:
    for i, j in bombs:
        if i in row_idx and j in col_idx:
            points -= 1
    if points == 0:
        print(ans-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
bombs = []
rows = [[]for _ in range(H)]
cols = [[]for _ in range(W)]
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    bombs.append((h, w))
    rows[h].append(w)
    cols[w].append(h)

max_row = 0
row_idx = set()
for i, row in enumerate(rows):
    if max_row < len(row):
        max_row = len(row)
        row_idx = {i}
        continue
    elif max_row == len(row):
        row_idx.add(i)

max_col = 0
col_idx = set()
for i, col in enumerate(cols):
    if max_col < len(col):
        max_col = len(col)
        col_idx = {i}
        continue
    elif max_col == len(col):
        col_idx.add(i)

ans = max_row+max_col
points = len(row_idx)*len(col_idx)
if M < points:
    print(ans)
else:
    for i, j in bombs:
        if i in row_idx and j in col_idx:
            points -= 1
    if points == 0:
        print(ans-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().strip().split())
h=[0 for _ in range(H)]
w=[0 for _ in range(W)]

dp=[]
for m in range(M):
    i,j=map(int,input().strip().split())
    dp.append((i,j))
    h[i-1]+=1
    w[j-1]+=1

h_max=0
hmax_l=[]
for i in range(H):
    if h_max==h[i]:
        hmax_l.append(i+1)
    elif h_max<h[i]:
        h_max=h[i]
        hmax_l=[]
        hmax_l.append(i+1)
w_max=0
wmax_l=[]
for i in range(W):
    if w_max==w[i]:
        wmax_l.append(i+1)
    elif w_max<w[i]:
        w_max=w[i]
        wmax_l=[]
        wmax_l.append(i+1)

cnt=0
for m in range(M):
    if h[dp[m][0]-1]+w[dp[m][1]-1]==h_max+w_max:
        cnt+=1

ans=h_max+w_max if cnt<len(hmax_l)*len(wmax_l) else h_max+w_max-1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
ans = 0
H, W, M = map(int, input().split())
HW = set()
Hlist, Wlist = [], []
for _ in range(M):
    h, w = map(int, input().split())
    Hlist.append(h)
    Wlist.append(w)
    HW.add((h,w))

cntH = Counter(Hlist)
cntW = Counter(Wlist)

maxhk, maxhv = cntH.most_common()[0]
ans = max(ans, maxhv)
for i in range(1,1+W):
    tmp = cntW[i]
    if (maxhk, i) in HW:
        tmp -= 1
    ans = max(ans, tmp+maxhv)

maxwk, maxwv = cntW.most_common()[0]
ans = max(ans, maxwv)
for i in range(1,1+H):
    tmp = cntH[i]
    if (i, maxwk) in HW:
        tmp -= 1
    ans = max(ans, tmp+maxwv)

print(ans)

Submission status: Accepted

Solution code:
# Date [ 2020-08-23 14:02:31 ]
# Problem [ e.py ]
# Author Koki_tkg
# After Contest

import sys;          from decimal import Decimal
import math;         from numba import njit, i8, u1, b1
import bisect;       from itertools import combinations, product
import numpy as np;  from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints(x=0):  return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def solve(h,w,bomb):
    row = np.zeros(h, dtype=np.int64)
    column = np.zeros(w, dtype=np.int64)
    
    for y, x in bomb:
        row[y] += 1
        column[x] += 1
        
    max_row = np.max(row)
    max_col = np.max(column)
    val = max_row + max_col

    max_row_lis = np.ravel(np.where(row == row.max()))
    max_col_lis = np.ravel(np.where(column == column.max()))

    for r in max_row_lis:
        for c in max_col_lis:
            if (r, c) not in bomb:
                return val
    
    return val - 1
    

def Main():
    h, w, m = read_ints()
    bomb = set([tuple(read_ints(x=1)) for _ in range(m)])
    
    print(solve(h, w, bomb))


if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W,M = LMIIS()
    targets_row = []
    targets_column = []
    targets = []
    for i in range(M):
        column,row = LMIIS()
        targets_row.append(row)
        targets_column.append(column)
        targets.append((column,row))

    common_columns = Counter(targets_column).most_common()
    common_rows = Counter(targets_row).most_common()
    max_columns = defaultdict(bool)
    num_max_column = common_columns[0][1]
    for k,v in common_columns:
        if v < num_max_column:
            break
        max_columns[k] = True
    max_rows = defaultdict(bool)
    num_max_row = common_rows[0][1]
    for k,v in common_rows:
        if v < num_max_row:
            break
        max_rows[k] = True
    dbg(max_columns)
    dbg(max_rows)
    num_candidates = len(max_columns)*len(max_rows)
    

    num_target_on_intersection = 0
    for column, row in targets:
        if max_columns[column] and max_rows[row]:
            num_target_on_intersection += 1
    
    ans = common_columns[0][1] + common_rows[0][1]
    dbg(num_target_on_intersection)
    dbg(num_candidates)
    print(ans if num_target_on_intersection < num_candidates else ans - 1)
    

    
    
    

    
main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
HW = set(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))

sum_h = [0]*H; sum_w = [0]*W
for h, w in HW:
    sum_h[h] += 1
    sum_w[w] += 1

max_h_num = 0
h_num_ix = {}
for i in range(H):
    num = sum_h[i]
    if num == 0: continue
    if not num in h_num_ix: h_num_ix[num] = set()
    h_num_ix[num].add(i)
    max_h_num = max(max_h_num, num)

max_w_num = 0
w_num_ix = {}
for i in range(W):
    num = sum_w[i]
    if num == 0: continue
    if not num in w_num_ix: w_num_ix[num] = set()
    w_num_ix[num].add(i)
    max_w_num = max(max_w_num, num)

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

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
  
counth = deque(counth)
countw = deque(countw)

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False


index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)


if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  for K in kouho:
    if binary_search(bomb, K):
      continue
    else:
      ans += 1
      break
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for _ in range(H)]
countw = [0 for _ in range(W)]
for _ in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1


maxh = max(counth)
maxw = max(countw)

counth = deque(counth)
countw = deque(countw)

index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
lenh = len(index_h)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
    lenw = len(index_w)
    if lenh*lenw > M:
      print(maxh + maxw)
      exit()    

ans = maxh + maxw - 1

bomb.sort()
bomb = deque(bomb)
kouho = []
for i in range(lenh):
  h = index_h.pop()
  for j in range(lenw):
    w = index_w[j]
    kouho.append(h+ H*w)
kouho.sort()
kouho = deque(kouho)
B = bomb.popleft()
K = kouho.popleft()
while True:
  if B > K:
    ans += 1
    break
  elif B == K:
    if len(kouho) == 0:
      break
    else:
      K = kouho.popleft()
  else:
    if len(bomb) == 0:
      ans += 1
      break
    else:
      B = bomb.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

counth = deque(counth)
countw = deque(countw)

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
lenh = len(index_h)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
    lenw = len(index_w)
    if lenh*lenw > M:
      print(maxh + maxw)
      exit()    

ans = maxh + maxw - 1

bomb.sort()
bomb = deque(bomb)
kouho = []
for i in range(lenh):
  h = index_h.pop()
  for j in range(lenw):
    w = index_w[j]
    kouho.append(h+ H*w)
kouho.sort()
kouho = deque(kouho)
B = bomb.popleft()
K = kouho.popleft()
while True:
  if B > K:
    ans += 1
    break
  elif B == K:
    if len(kouho) == 0:
      break
    else:
      K = kouho.popleft()
  else:
    if len(bomb) == 0:
      ans += 1
      break
    else:
      B = bomb.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

counth = deque(counth)
countw = deque(countw)

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  bomb = deque(bomb)
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  kouho.sort()
  kouho = deque(kouho)
  B = bomb.popleft()
  K = kouho.popleft()
  while True:
    if B > K:
      ans += 1
      break
    elif B == K:
      if len(kouho) == 0:
        break
      else:
        K = kouho.popleft()
      if len(bomb) == 0:
        ans += 1
        break
      else:
        B = bomb.popleft()
    else:
      if len(bomb) == 0:
        ans += 1
        break
      else:
        B = bomb.popleft()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

counth = deque(counth)
countw = deque(countw)

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  bomb = deque(bomb)
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  kouho.sort()
  kouho = deque(kouho)
  B = bomb.popleft()
  K = kouho.popleft()
  while True:
    if B > K:
      ans += 1
      break
    elif B == K:
      if len(kouho) == 0:
        break
      else:
        K = kouho.popleft()
    else:
      if len(bomb) == 0:
        ans += 1
        break
      else:
        B = bomb.popleft()
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc176/submissions/16124424
from collections import Counter
def abc176_e():
  h, w, m = map(int, input().split())
  H = []
  W = []
  for _ in range(m):
    hi, wi = map(int, input().split())
    H.append(hi)
    W.append(wi)
  mosth = Counter(H).most_common()[0]
  mostw = Counter(W).most_common()[0]
  ans1 = mosth[1]
  ans2 = mostw[1]
  wpair = []
  hpair = []
  for i, hi in enumerate(H):
    if hi == mosth[0]: continue
    wpair.append(W[i])
  for i, wi in enumerate(W):
    if wi == mostw[0]: continue
    hpair.append(H[i])
  if wpair:
    ans1 += Counter(wpair).most_common()[0][1]
  if hpair:
    ans2 += Counter(hpair).most_common()[0][1]
  ans = max(ans1, ans2)
  print(ans)

if __name__ == '__main__':
    abc176_e()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
R = [0]*H #各行にある爆弾の個数
C = [0]*W #各列にある爆弾の個数
bombs = []
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    R[h] += 1
    C[w] += 1
    bombs.append((h, w))

R_max = max(R)
C_max = max(C)

### Rが最大かつCが最大な座標であって、
# そこに爆弾がない場合があれば
# 答えがR_max+C_max
# なければR_max+C_max-1
count = 0 # 爆弾がある座標であって、Rが最大かつCが最大の組の個数
for bx, by in bombs:
    if R[bx] == R_max and C[by] == C_max:
        count += 1

count_R = R.count(R_max)
count_C = C.count(C_max)
if count >= count_R*count_C:
    ans = R_max + C_max - 1
else:
    ans = R_max + C_max
print(ans)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
HW = set(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))

sum_h = [0]*H; sum_w = [0]*W
for h, w in HW:
    sum_h[h] += 1
    sum_w[w] += 1

h_num_ix = {}
for i in range(H):
    num = sum_h[i]
    if num == 0: continue
    if not num in h_num_ix: h_num_ix[num] = set()
    h_num_ix[num].add(i)

w_num_ix = {}
for i in range(W):
    num = sum_w[i]
    if num == 0: continue
    if not num in w_num_ix: w_num_ix[num] = set()
    w_num_ix[num].add(i)

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

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

Submission status: Accepted

Solution code:
from collections import deque
import heapq
H, W, M = map(int, input().split())
bomb = []
heapq.heapify(bomb)
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  heapq.heappush(bomb, h+ w*H)
  counth[h] += 1 
  countw[w] += 1

counth = deque(counth)
countw = deque(countw)

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  kouho = []
  heapq.heapify(kouho)
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      heapq.heappush(kouho, h+ H*w)
  B = heapq.heappop(bomb)
  K = heapq.heappop(kouho)
  while True:
    if B > K:
      ans += 1
      break
    elif B == K:
      if len(kouho) == 0:
        break
      else:
        K = heapq.heappop(kouho)
    else:
      if len(bomb) == 0:
        ans += 1
        break
      else:
        B = heapq.heappop(bomb)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1
counth = deque(counth)
countw = deque(countw)

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False


maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)


if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  for K in kouho:
    if binary_search(bomb, K):
      continue
    else:
      ans += 1
      break
    
print(ans)

Submission status: Accepted

Solution code:
def main():
  h,w,m = map(int, input().split())
  hl = [0] * h
  wl = [0] * w
  dic = set()
  for i in range(m):
    x,y = map(int, input().split())
    dic.add((x,y))
    hl[x-1] += 1
    wl[y-1] += 1

  h_max = max(hl)
  r = [i for i in range(h) if hl[i] == h_max]
  w_max = max(wl)
  c = [i for i in range(w) if wl[i] == w_max]

  flg = 0
  for rc in r:
    for cc in c:
      if (rc+1,cc+1) not in dic:
        print(h_max + w_max)
        return

  print(h_max + w_max - 1)
  
if __name__ == '__main__':
    main()