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 statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
H,W,M = readInts()

dic1 = Counter()
dic2 = Counter()
s = set()
for i in range(M):
    h,w = map(lambda x:int(x)-1, input().split())
    dic1[h] += 1
    dic2[w] += 1
    s.add((h,w))
# print(dic)
ans = 0

# 重なっているもので最大値がある時もあれば
# 行、列の交差点でボムなしが一番大きいものがある
for h,w in s:
    ans = max(ans, dic1[h] + dic2[w] - 1)

dic1 = dic1.most_common()
dic2 = dic2.most_common()
max1 = dic1[0][1]
max2 = dic2[0][1]

for k1,v1 in dic1:
    if v1 < max1:
        break # continueする必要がない most_commonで大きい方から集めてるので
    for k2,v2 in dic2:
        if v2 < max2:
            break # 同じく
        if (k1,k2) in s: # 一度計算したもの
            continue
        # 両方とも最大であればok
        ans = max(ans, v1 + v2)
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


H, W, M, *hw = map(int, open(0).read().split())
h_cnt = Counter(hw[::2])
w_cnt = Counter(hw[1::2])
h_max = h_cnt.most_common(1)[0][1]
w_max = w_cnt.most_common(1)[0][1]

not_on_bomb = sum(1 for k, v in h_cnt.items() if v == h_max)
not_on_bomb *= sum(1 for k, v in w_cnt.items() if v == w_max)
for h, w in zip(*[iter(hw)] * 2):
    if h_cnt[h] == h_max and w_cnt[w] == w_max:
        not_on_bomb -= 1

ans = h_max + w_max
print(ans) if not_on_bomb else print(ans - 1)

Submission status: Accepted

Solution code:
def main():
    H, W, M = map(int, input().split())
    cnth = [[0, i] for i in range(H)]
    cntw = [[0, i] for i in range(W)]
    L = set()
    for _ in range(M):
        h, w = map(lambda x: int(x) - 1, input().split())
        cnth[h][0] += 1
        cntw[w][0] += 1
        L.add((h, w))
    cnth.sort(reverse=True)
    cntw.sort(reverse=True)
    mh = set()
    ph = cnth[0]
    for h in cnth:
        if ph[0] == h[0]:
            mh.add(h[1])
        else:
            break
        ph = h
    mw = set()
    pw = cntw[0]
    for w in cntw:
        if pw[0] == w[0]:
            mw.add(w[1])
        else:
            break
        pw = w
    maxans = cnth[0][0] + cntw[0][0]
    for h in mh:
        for w in mw:
            if not ((h, w) in L):
                print(maxans)
                break
        else:
            continue
        break
    else:
        print(maxans - 1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
boms = []
h, w = [0] * (H + 1), [0] * (W + 1)
for _ in range(M):
    h_, w_ = map(int, input().split())
    boms.append([h_, w_])
    h[h_] += 1
    w[w_] += 1

hmax = max(h)
wmax = max(w)

cnt = h.count(hmax) * w.count(wmax)
for hh, ww in boms:
    if hmax == h[hh] and wmax == w[ww]:
        cnt -= 1

print(hmax + wmax - (cnt == 0))

Submission status: Accepted

Solution code:
from collections import defaultdict
h, w, m = map(int, input().split())

row = [[0, 0] for _ in range(h + 1)]
col = [[0, 0] for _ in range(w + 1)]
ex = defaultdict(bool)
for i in range(m):
    r, c = map(int, input().split())
    row[r][0] += 1
    col[c][0] += 1
    row[r][1] = r
    col[c][1] = c
    ex[(r, c)] = True
row = sorted(row)[::-1]
col = sorted(col)[::-1]
ans = 0
for i in range(0, h + 1):
    for j in range(0, w + 1):
        ans = max(ans, row[i][0] + col[j][0] - ex[(row[i][1], col[j][1])])
        if not ex[(row[i][1], col[j][1])]:
            # iが同一だったら、jの値降順に見てるので木って良い
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,Counter

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

w_list = []
h_list = []

se = set()

for _ in range(m):
    nh,nw = map(int,input().split())

    se.add((nh,nw))
    w_list.append(nw)
    h_list.append(nh)

w_count = Counter(w_list)
h_count = Counter(h_list)

max_w = 0
max_h = 0

ch = []
cw = []

for i in w_count.values():
    max_w = max(max_w,i)
    cw.append(i)

for i in h_count.values():
    max_h = max(max_h,i)
    ch.append(i)

ma = ch.count(max_h)*cw.count(max_w)

result = max_h+max_w
point = 0

for i,j in se:
    if w_count[j] == max_w and h_count[i] == max_h:
        point += 1

if point == ma:
    print(result-1)
else:
    print(result)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * (h+1)
    w_lis = [0] * (w+1)
    bombs = set([tuple(map(int,input().split())) for i in range(m)])
    for hh, ww in bombs:
        h_lis[hh] += 1
        w_lis[ww] += 1
    max_h = max(h_lis)
    max_w = max(w_lis)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max_h]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max_w]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not (h_i, w_i) in bombs:
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


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


def main():
    h, w, m = [int(i) for i in input().split()]
    d_h = defaultdict(int)
    d_w = defaultdict(int)
    bom = set()
    for _ in range(m):
        h, w = [int(i) for i in input().split()]
        bom.add((h, w))
        d_h[h] += 1
        d_w[w] += 1
    H = sorted(d_h.items(), key=lambda x: -x[1])
    W = sorted(d_w.items(), key=lambda x: -x[1])
    ans = 0
    for k_h, v_h in H:
        for k_w, v_w in W:
            tmp = v_h + v_w
            if (k_h, k_w) in bom:
                tmp -= 1
                ans = max(tmp, ans)
            else:
                ans = max(tmp, ans)
                break
        else:
            continue
        break

    for k_w, v_w in W:
        for k_h, v_h in H:
            tmp = v_h + v_w
            if (k_h, k_w) in bom:
                tmp -= 1
                ans = max(tmp, ans)
            else:
                ans = max(tmp, ans)
                break
        else:
            continue
        break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W,M = map(int,input().split())
X = {}
CH = {}
CW = {}
for _ in range(M):
    h,w = map(int,input().split())
    X[(h,w)] = 1
    if h not in CH:
        CH[h] = 0
    CH[h] += 1
    if w not in CW:
        CW[w] = 0
    CW[w] += 1
hmax = 0
for h in CH:
    hmax = max(hmax,CH[h])
A = []
for h in CH:
    if CH[h]==hmax:
        A.append(h)
wmax = 0
for w in CW:
    wmax = max(wmax,CW[w])
B = []
for w in CW:
    if CW[w]==wmax:
        B.append(w)
flag = 0
for h in A:
    for w in B:
        if (h,w) not in X:
            flag = 1
            break
    if flag==1:break
if flag==1:
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())
s = set()
ys = [0] * (H + 1)
xs = [0] * (W + 1)
for _ in range(M):
  y, x = map(int, input().split())
  s.add((y, x))
  ys[y] += 1
  xs[x] += 1

res = 0
mxy = []
mx = max(ys)
for i in range(H + 1):
  if ys[i] == mx: mxy.append(i)
res += mx

mxx = []
mx = max(xs)
for i in range(W + 1):
  if xs[i] == mx: mxx.append(i)
res += mx - 1

for x in mxx:
  for y in mxy:
    if (y, x) in s: continue
    res += 1
    break
  else: continue
  break
print(res)

Submission status: Accepted

Solution code:
import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

h, w, m = map(int, input().split())
R = [0]*h
C = [0]*w
YX = []
for i in range(m):
    y, x = map(int, input().split())
    y, x = y-1, x-1
    R[y] +=1
    C[x] +=1
    YX.append((y, x))

max_r = max(R)
max_c = max(C)
cr = 0
cc = 0
for i in range(h):
    if R[i] == max_r:
        cr += 1
for i in range(w):
    if C[i] == max_c:
        cc +=1
c = 0
for y, x in YX:
    if R[y] == max_r and C[x] == max_c:
        c += 1
if c < cr*cc:
    print(max_r+max_c)
else:
    print(max_r+max_c-1)

Submission status: Accepted

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

cntH = [0] * (H + 1)
cntW = [0] * (W + 1)
for h, w in bombs:
    cntH[h] += 1
    cntW[w] += 1

mxH = max(cntH)
mxW = max(cntW)

ans = mxH + mxW - 1

mxH = [h for h in range(1, H + 1) if cntH[h] == mxH]
mxW = [w for w in range(1, W + 1) if cntW[w] == mxW]

for h in mxH:
    for w in mxW:
        if not (h, w) in bombs:
            ans += 1
            print(ans)
            exit()
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, M = [int(s) for s in input().split()]
    cols = [0] * W
    rows = [0] * H
    bombs = set()
    for _ in range(M):
        x, y = [int(s)-1 for s in input().split()]
        bombs.add((x, y))
        cols[y] += 1
        rows[x] += 1

    sc = sorted([(c, i) for i, c in enumerate(cols)], reverse=True)
    sr = sorted([(c, i) for i, c in enumerate(rows)], reverse=True)
    best = 0
    for v1, c in sc:
        for v2, r in sr:
            if v1 + v2 <= best:
                break
            score = v1 + v2
            if (r, c) in bombs:
                score -= 1
            best = max(best, score)
    print(best)

main()

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
h = [0 for _ in range(H+1)]
w = [0 for _ in range(W+1)]
hmax = 0
wmax = 0
Q = []
for _ in range(M):
  a, b = map(int, input().split())
  Q.append((a, b))
  h[a] += 1
  hmax = max(hmax, h[a])
  w[b] += 1
  wmax = max(wmax, w[b])
h_ok = False
w_ok = False
hm = [False for _ in range(H+1)]
wm = [False for _ in range(W+1)]
h_cnt = 0
w_cnt = 0
hw_cnt = 0
for a, b in Q:
  if not hm[a] and h[a] == hmax:
    hm[a] = True
    h_cnt += 1
  if not wm[b] and w[b] == wmax:
    wm[b] = True
    w_cnt += 1
  if h[a] == hmax and w[b] == wmax:
    hw_cnt += 1
if h_cnt*w_cnt - hw_cnt > 0:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)

Submission status: Accepted

Solution code:
def main(): 
    h,w,m = map(int,input().split())
    X = [0]*w
    Y = [0]*h
    g = set([])
    for _ in range(m):
        a,b = map(int,input().split())
        a-=1
        b-=1
        X[b]+=1
        Y[a]+=1
        g.add((a,b))
    
    xmax = max(X)
    ymax = max(Y)

    xlist = []
    for i,x in enumerate(X):
        if x==xmax:
            xlist.append(i)
    ylist = []
    for i,y in enumerate(Y):
        if y==ymax:
            ylist.append(i)
    
    ans = xmax+ymax
    flag = True
    for x in xlist:
        for y in ylist:
            if (y,x) not in g:
                flag = False
                break
        if not flag:
            break
    
    if flag:
        ans-=1
    print(ans)
main()

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
h=[]
w=[]
for i in range(m):
  h_,w_=map(int,input().split())
  h.append(h_)
  w.append(w_)
from collections import Counter
dic_h=Counter(h)
dic_w=Counter(w)
max_h=max(dic_h.values())
max_w=max(dic_w.values())

h_set=set()
w_set=set()
for i in dic_h:
  if dic_h[i]==max_h:
    h_set.add(i)
for j in dic_w:
  if dic_w[j]==max_w:
    w_set.add(j)

cnt=0
for i in range(m):
  if h[i] in h_set and w[i] in w_set:
    cnt+=1
if len(h_set)*len(w_set)>cnt:
  print(max_h+max_w)
else:
  print(max_h+max_w-1)

Submission status: Accepted

Solution code:
H, W, M = map(int, input().split())
hws = [list(map(lambda x :int(x)-1, input().split())) for _ in range(M)]

booms = [set() for _ in range(H)]

yoko = [0 for _ in range(W)]
tate = [0 for _ in range(H)]

for hw in hws:
    tate[hw[0]] += 1
    yoko[hw[1]] += 1
    booms[hw[0]].add(hw[1])
    
max_tate = max(tate)
max_yoko = max(yoko)


tate_candidates = []
yoko_candidates = []

for i in range(H):
    if tate[i] == max_tate:
        tate_candidates.append(i)
        
for i in range(W):
    if yoko[i] == max_yoko:
        yoko_candidates.append(i)

exist = 0
for tate_candidate in tate_candidates:
    for yoko_candidate in yoko_candidates:
        if yoko_candidate not in booms[tate_candidate]:
            exist = 1
            break
    else:
        continue
    break
print(max_tate + max_yoko + (exist-1))

Submission status: Accepted

Solution code:
H,W,M = map(int, input().split())
hs = [0] * H
ws = [0] * W
s = set()
for i in range(M):
  h,w = map(int, input().split())
  h -= 1
  w -= 1
  s.add((h,w))
  hs[h] += 1
  ws[w] += 1
  
mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])
  
i_s = list()
j_s = list()
for i in range(H):
  if mh == hs[i]:
    i_s.append(i)
for j in range(W):
  if mw == ws[j]:
    j_s.append(j)
ans = mh + mw
for i in i_s:
  for j in j_s:
    if (i,j) in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)

Submission status: Accepted

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

for i in range(m):
    hi, wi = list(map(int, input().split()))
    ms.append((hi - 1, wi - 1))
    hs[hi - 1] += 1
    ws[wi - 1] += 1

maxh = max(hs)
maxw = max(ws)
cnt_h = sum([hs[i] == maxh for i in range(h)])
cnt_w = sum([ws[i] == maxw for i in range(w)])
cnt = cnt_h * cnt_w

for x, y in ms:
    if hs[x] == maxh and ws[y] == maxw:
        cnt -= 1

if cnt <= 0:
    print(maxh + maxw - 1)
else:
    print(maxh + maxw)

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
# Original source code : 

"""
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int h, w, m; cin >> h >> w >> m;
  vector<pair<int, int>> in;

  vector<int> cnt_row(h, 0), cnt_col(w, 0);

  for (int i = 0; i < m; ++i) {
    int hh, ww; cin >> hh >> ww;
    --hh; --ww;
    in.emplace_back(hh, ww);
    ++cnt_row[hh]; ++cnt_col[ww];
  }

  int mx_row = *max_element(all(cnt_row));
  int mx_col = *max_element(all(cnt_col));
  int ans = mx_row + mx_col;
  int64 can = count(all(cnt_row), mx_row) * count(all(cnt_col), mx_col);
  if (can > m) {
    cout << ans << endl;
  } else {
    int bad = 0;
    for (auto e : in) bad += (cnt_row[e.first] + cnt_col[e.second] == ans);
    if (can > bad) {
      cout << ans << endl;
    } else {
      cout << ans - 1 << endl;
    }
  }

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%1E9eQ+Dcb>9O(5t1kX`mjt%mI*tQL&XwINR&jxkwuUMd5DiP!w*|+EuBCB6k&q^0~{n$Bd1JBy1CGB7>|>vjWSi;W~N``DCsnHKRh8#SszW>krOp`B|Fxnk^_XMEk}te*%r~ad%M8h@y<>&{gcZ9-o4+x_xA1Ey}jGT;~xfu77NEAR;=g&gt-$Ag>RsE-{ztSVD)G*eBX)IqeZ~mRC0QHgVR!bu^mOP-lFh&dI!={PDRU*d3kq*mLlXX>S15&*VA^^yEXI@ZI>_8>RG5>JJoBa@{GEu9;2*(Hu~wJxSlp6EwxeFenpDl>+>#!*HZy$DbxEL=q*COeWB)12W`(RE@!B}jIwdKFCOdJUUy$SvN;}0WCk}6)^Fduz0Q+PdbSXsTvWDocQ=v8<84v-yozGDzIE{f7cLG(clEz6)Of!6+$)dFe(eD)yAqYg4M&&*&6U)~s-qQ6>93bFlk>_c_^dF%-!j3!3=Q3FfIns;-)(|F!5QOkn#iv=k&m0;pD@AgCis4ncB>GZ;o8z^V&_jxaF>al`%UoYP5ikZ>@P=aP=j01a?y$QZKUA)?^5teHUVM&rKL#t-h1(!+m1x>Kz}kJrln9y5=A5iyV}G^G!;D%OH0vIS6fp&nTU3Udg4)~&ba3HcX!58=|D$}Tqfh`0KV#!>Y|BAJQ(hjyxwqMC?!g%P)te(!+}5tU|V}a=~!4yrlnLg)F12;yK2Qi=XQ~(ZVks0#F|teOQuB-jn)MdF{#-bI7kG%J48|HOC=9MT|^AU<H<0th{W3u>h!$Z(nE=`cqk_IK}RF8WS|H4dvH)3h^ErXL?|AUhQx!lpq4n)Z`5cLYqTz$%t$zf2f|@7jYH@~Vt3+DED;eqqUlV36jz2>Y$2@S$Hj2p<6>_p76%|a7!pHLbTB4SrZ<M0KMXMxu_7Ia{t$G&wW&$m>ZwJoLa?z(+~TP#UTyJgLrr`3_#1<w*RxfD_v``TI)qmX3#<^OZyS8d=z44=Q@}$0l)}MZfGf?%_IrkwV#&YdSiJ@H(E3{Vtct~!;g#s`DVA9qTZ~tv7gh2cDy@@0`Of2I_{npY%1axcv11R;Q+c*tvi1LjQ=ttye3(90c^y7L<?U`Q&iHdx3dL)oRdwIIroxx0@JlM(slszA+@->=s_^A1{Dulw-?uL67w-O270&Ko{1{!S!rA?c@l`5(klHUtrDqE+!zx_8$bU(N+f?|33Rk}$997}!=i_k|UarFbN`>21_z4xhScSi!!k4J<Nfln9!q2F1hYIIM-nR4OW!<aYh##AjEQNFY$VvM&Dr|e{Ha9A4I0@g*ss^~id>>ZHUn)S^@XwgXq065m{P!@ALzbT;{NG?6PnrA)!as+39J>5*!v87eamex$gntI}I8^yz!had_*xmd9;r|HpI5heFgg=aV9FlxH;ZvB$p~yE7{xRTtCs;rIkN6+<7X01*uI^6g^I(J@w{57w0g#)k`@EC6dqIcKO4WDp*_}VY(Kuap>~<w)0>GR2?4#A~xeZjx&C92Am6WN*%u>vRiT;u5T0wq~moJ=du5QN$a{mGS#+7aXDr*G!SG@ctRBj^H<(s+Zp<W0J)zyKqv(BeI5Y>Qp)_XDFz3iQxsmJk`SISK`eq<U3OQ^2p!$0Q7!T89_+=%U~93Sqg-ZWyH;D`;sFYkQ%L)^9O&fh=~1bHskKUXLS@^$QJ4_tz7O|~7AO>$Rt%}9<5`rd#*Y|4CtmtPY$Ucyna^HVphFe#j)oCODA6B2wm=acx2Gx%abDOJI#D^@{%H}@H^ie0mhgS~MaFK$Zk{kOba{=CgOx)$qXp_bqHLw;(;%4h4|z(eW1=&TwgF%FJb+`-Egm86TlYngX>ZW>>=ja`;j3-T|BL%CD8z;|c>citZ4UJlA9^E0Gn2nLA^37WGC3FD7e*N^*xz8^YAzsTWX{<oPWfRAtS{f|?a<40by3BC)Ns{)wYBlylaN5244&Ep{W(#+D{iSaFd-_>TPa7vN<apoN`)tId-caDBnG3TAd;{xO4`?TNr?8`)sn+^JYl9?g)s)*Q2-h#8L8IR}1W}gKFrxn3BgJAQQyz@J^g1(zac0s6|qxfA)kbfTVp6#6w!YhPuqpfA!Hr!&heHEMm-AT~32b|xZ3~*CCG<2aYd=}K7NWw_ZtZ<{;TOUF!V2l%(jvs-Tj1{D^+*c@DtFXhs;<(x&uDLWY-boz0z6igyg4`3%u`#kVoE-dvz5Yl2d;R<T;<TSUqVh{|xU)NtKyxGSa5)LoXP)9;D9#7p%g#T3;}*8rHa6=V&B0~<Rro3fdh8ou!CLQ~mFK*L{QKCPJe_v|h3NaUb@ll_gKG#v{!TEMyY>O=iaf2jKlOp8H{bg})thhQI{D4qETPjd7iP`_otg2@=96Hym(4fm!mn1k$?}&wP7Ll0EeAe(+hc@mJ5Op)+VhQ2+dJW%4a%?V<K>_8BbTqXcL~|D_wo2<myHmz^B71KZd(Mpzb4}ikQbP4K3ldC8}!}a<tx$}SZXi0l%;mr-om9`5A$d5G@eZ*9`xUH5l4RM!e%zkfj&PqXXWLq{8Vli&z<65nUgBP;Ga{271*Gez2Ti4bO>ec<41Nr1PWjh{HcI$9|kV>@9#sXdFaBavj2jS<*@oN*1I;{OZtPw_vU*GB!s}zl~le(9w1}a`P1ZS#-DDrQ%aul(j&#Gv5S|l@xD`sf<m_XAIL2)|0f<Y3pDK???#`^eg;<60NgWAxOyjK7e6uy3*HQu`86PRJQT`goF?si3p2Ugft!T_^%Jk}LHSkemXO`>(+U#$%|8R$>6dQ><?F)6E5y~QTh?4T=<#E-lDoA22=e=|J~qqm`U|UGhlPjZeQ&`1S!|Wu0u!ZpUYn-RPV%&*?``X>_wz`3e*fr3q3|rwr=Y2S1$qo<ElicagIi$~=<7fufWHls@;uNZ5TRp$zYX*<S9(|B4tF4K(8aB*D7Q~=<t~ilvxx!FzgP7fH<m}Jn#$LLKa*I%;c9VIe%874kbM~KT6_PewpQQG^zoU%8IV)If7HY0QTX8dQ^r7}!<Dr(Ix3&C`W@~kZGK11NLj0+)^cEpqXrPaqY@+<9rl)`r8AVn?E>+t{F`eWZnTd1hM$etzX-Hh4o^VazbN*<g6%(TZFab`wnj(IQ)PZf?URfAj{1@EX2%K6`bp~&M?GNBcB8}H$XfI-rTwS?+iqBwJh<@(9j<*2JLy|B;IBd4qDa$Dpx6$N+u?CLZH|VNQ5)pl74MM|#6$glSSWDo+yU5!mwix<zQvVYD@SwO&ulN2qj$<b>fC6dER=<^P!`HUSttu-p)8b-D(rlho#(RiTlMdhY8v3Qd=I@~XM<m&hl=bB_ar@>T|;?xzPyg|?Cf?erR+SJz3a2R!*AvaNlcH@mt^)1`~p2ZWoM$3w4R+|UZVc7v)xKcZ$sL`&Z76zb4~UxZm0TeKg7;hZ>MzFuEqIst>5)jpPjX`_U}YmIoR%#{&5tVqx>1#u>$3ppI0e=l-A#*y!tHp|Ff{)iS_0Cv}30z{VAnyQF@)yMRY(`Q+f}j+bM0K^kMbk^Y2jD?+mQ8HZ^_PUDMr@Nk|#@4$n4E?dGi+!g;^ot@qT{ZB)?T#<mqkr{3U~TKv0CmmzLNk|Ay@&SNcJR-C_Dd{J?pYw_~p_-k={ao%Y0#l`ul#g`Q4u@+xiyq~pr1v+ksFGKqc#?OizXuuG67S{(Y?n37b@#V$*0WH1)xtAN^E73WFA8D;{H`g1?XDh4<ydl2YaQ<6i6=3Uy7KgjsZG@M87uMoy=V5r+u%Y(~dK`z{0`X+)wTI&CiOw1{bho>xkIN<#J3FYIOAamWqqy6t#RZBF=<pue?x3#S&y(x<@jOcHoY2|%OCmpiT+IAe&d64v9~q3Vk^C#<d;a{nOzg}b-&yj#YM%dd6xaK?oWpkJ&xcQv-&reBrEc8+$%231oj*@JB!8eZ|JiN7(<E;pY=S>yk_UpHKPy!CV>xZ$c@sO=u|Jl|dF!gxVl2N7@Vh{s{jSQEm19;cKmUH;VPfZVCisgM#ebI9#m+3FCh~(OxSRMhe|>w_qV!ikUdJuQc^&^~QN~w4jyJIk$PeGG#ZOxBxH!-xo&Pe$uUHg$eY@|O_`lk!#G#$WGfMG$tj6-KCip(9aem8T6ZvOoyOXqC_PBb^YMkHlf{C41t;TV<Vd4*-r$+c)He>q;r)+q_VI;N+4>kG)QA}rg#GsPNfip*hdQpreV~LoA!YL^&WqNx(VN^=B5v6`Hj8kgTNE9PU@jyJ;6N-xwDVa)(q0Ar(C;JEDQ7Ibn?AY$BHx|O_Br!3RN`;2RXhKR2q25%eKPpBt{ry9rqT)pCibhlvTRQx00Wq+<8D|2Ct-HI$08c@_xdVyKzqi}p7Hon#jdDZ_kQA0;93E<E=?rv<UH(QP09K=skQ72<@F9|klMplMXv8#~r=dZe+VZhUJvwnsehsao$uqxuZj!!@NIEI@g}{<J3rZ{0{D>zN?e!RE9H}yb^e*B|CVd1Fhx+v%XmgB8MsQtMTN4{jmb^5t127(J$Z&wSAB=`!It62$p<pZ!Xz~X7J06U6JlI)_=R{9Btrni2C8ak{lA6Nl44EK?Syv4Ws#K<8`k2nnN2R4{(yu^|rcJ5Z#&<<Asm##BQreY%6bwSLMH7<w`E#Z@at5hvT5pgiJ=8CSdVoqPh4!(lSOQEAAWtGGMLiI&%~I$9<qjk=o}NrB9@!j=Aj0*9(tXGi8A^aXg-R)<<{$(=mP}|E5$aOWcnAy9tAV(Ln}jjLm!1PjxPVy--z1oxRFd4to@gIkRQe*R5(n19VKF)wjt)qoMEdV3tq_V0b`5QY`eR|ZAO>NEArGu|{jew*t+W5fg7^LS(ZHS?X8F>ra60}INSjNg&qsFa<n`MouTG!s&ls)#7=8S^-*wn)Gkvy?W3-0i?0iDMt=f&0vk0co_Ir%7{Bpc~<5c?W+~8rP%|T}SLPjs?0;Z4OKBSx_6#ZYMrJvIIZ_&}mk#aV{c(%`EbQqQVx1#y|Ka7-^GJUomWt5$l=;O!wKT7o*DbMz;jM`QDw;Sj`jnui=rSmFA*|`oY`tg@_`fMM}=%h~GrK8X4^x1xyQGLAZI{Gc0K6{U6v_rS=*Ke2qLZ{E(#~Iac>-GKrYpT!Qx!68MzhBYoGx}Ymz5mVrFTkw*AL#VizMs((x(Tn3=UJUTJ0D=QN+++se=Z^=-;tfemHy8_;q~#>kKZqllE=#Q+5VDWZ|tvL{~FTf&X)d<gSJmQwn(SP{5neeq(AT6Pdk46W7_{vr(fLnP{Qsry*?`zdceu_*?y{$>Nn`lzZ!J<<($&K{=kmuZ`9#N=h#O7Y{66gGjtuo&mj+*zkV!M`K~T5y70H?Caiw`EH}}AcoVhrG3)pL0-|UQSp"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
H,W,M=map(int,input().split())
h=[0]*(H+1)
w=[0]*(W+1)
hw=[0]*M
for i in range(M):
  y,x=map(int,input().split())
  hw[i]=(y,x)
  h[y]+=1
  w[x]+=1
cnt=0
mxh=max(h)
mxw=max(w)
for hi,wi in hw:
  if h[hi]==mxh and w[wi]==mxw:
    cnt+=1
if h.count(mxh)*w.count(mxw)==cnt:
  print(mxh+mxw-1)
else:
  print(mxh+mxw)

Submission status: Accepted

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

hs = [0] * H
ws = [0] * W
s = set()
for i in range(M):
  h,w = map(int, input().split())
  h -= 1
  w -= 1
  hs[h] += 1
  ws[w] += 1
  s.add((h,w))
  
mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])
  
i_s = list()
j_s = list()
for i in range(H):
  if hs[i] == mh:
    i_s.append(i)
for j in range(W):
  if ws[j] == mw:
    j_s.append(j)
    
ans = mh + mw
for i in i_s:
  for j in j_s:
    if (i,j) in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
 
H, W, M = map(int, input().split())
 
X = [0] * W
Y = [0] * H
Map = []
 
for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    Y[h] += 1
    X[w] += 1
    Map.append((h, w))
 
MX = max(X)
MY = max(Y)
ans = MX + MY
Xans = set()
Yans = set()
for i, x in enumerate(X):
    if x == MX:
        Xans.add(i)
for i, y in enumerate(Y):
    if y == MY:
        Yans.add(i)
cnt = 0
for h, w in Map:
    if h in Yans and w in Xans:
        cnt += 1
if cnt == len(Xans) * len(Yans):
    ans -= 1
print(ans)

Submission status: Accepted

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

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

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

for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    Y[h] += 1
    X[w] += 1
    Map.append((h, w))

MX = max(X)
MY = max(Y)
ans = MX + MY
Xans = set()
Yans = set()
for i, x in enumerate(X):
    if x == MX:
        Xans.add(i)
for i, y in enumerate(Y):
    if y == MY:
        Yans.add(i)
cnt = 0
for h, w in Map:
    if h in Yans and w in Xans:
        cnt += 1
if cnt == len(Xans) * len(Yans):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    h,w,m=map(int, readline().rstrip().split())
    cntH=[0]*h
    cntW=[0]*w

    ys=[0]*m
    xs=[0]*m

    for i in range(m):
        y,x = map(int, readline().rstrip().split())
        y-=1
        x-=1
        cntH[y]+=1
        cntW[x]+=1
        ys[i]=y
        xs[i]=x
    maxX = max(cntW)
    maxY = max(cntH)
    cntMaxX=cntW.count(maxX)
    cntMaxY=cntH.count(maxY)
    cntMax=cntMaxX*cntMaxY

    for i in range(m):
        y=ys[i]
        x=xs[i]
        maxPtn=False
        if cntH[y]==maxY and cntW[x]==maxX:
            cntMax-=1
    if cntMax > 0:
        print(maxX+maxY)
    else:
        print(maxX+maxY-1)
    return


if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

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

hs = [0] * H
ws = [0] * W
s = set()

for i in range(M):
  h,w = map(int, input().split())
  h -= 1
  w -= 1
  hs[h] += 1
  ws[w] += 1
  s.add((h,w))

mh = 0
mw = 0
for i in range(H):
  mh = max(mh, hs[i])
for j in range(W):
  mw = max(mw, ws[j])
  
l_s = list()
j_s = list()
for i in range(H):
  if mh == hs[i]:
    l_s.append(i)
for j in range(W):
  if mw == ws[j]:
    j_s.append(j)
    
ans = mh+mw
for i in l_s:
  for j in j_s:
    if (i,j) in s:
      continue
    print(ans)
    exit()
ans -= 1
print(ans)

Submission status: Accepted

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

sumh = [0] * W
sumw = [0] * H
checkset = set()
for i in range(M):
    h, w = map(int, input().split())
    checkset.add((h-1, w-1))
    sumh[w-1] += 1
    sumw[h-1] += 1
shmax = max(sumh)
swmax = max(sumw)
sh = []
sw = []
for i, s in enumerate(sumh):
    if s == shmax: sh.append(i)
for i, s in enumerate(sumw):
    if s == swmax: sw.append(i)
ans = shmax + swmax - 1
jdg = False
for i in sh:
    for j in sw:
        if (j, i) not in checkset: 
            ans += 1
            jdg = True
            break

    if jdg: break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    H, W, M = list(map(int, input().split()))
    bombs = [list(map(int, input().split())) for _ in range(M)]
    counter_row = Counter([h for h, _ in bombs])
    val_max_row, max_rows = 0, []
    for h, v in counter_row.items():
        if val_max_row < v:
            val_max_row = v
            max_rows = [h]
        elif val_max_row == v:
            max_rows.append(h)
    counter_col = Counter([w for _, w in bombs])
    val_max_col, max_cols = 0, []
    for w, v in counter_col.items():
        if val_max_col < v:
            val_max_col = v
            max_cols = [w]
        elif val_max_col == v:
            max_cols.append(w)
    # 基本的には val_max_row + val_max_col が答え。
    # 行・列で重複カウントになるケースだった場合はここから1引かないといけない。
    max_rows = Counter(max_rows)
    max_cols = Counter(max_cols)
    n_max_cells = len(max_rows.keys()) * len(max_cols.keys())
    n_cells = 0
    for h, w in bombs:
        if max_rows[h] > 0 and max_cols[w] > 0:
            n_cells += 1
    ans = val_max_row + val_max_col
    if n_cells >= n_max_cells:
        ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

h,w,m = (int(x) for x in input().split())
rows = [[0,i] for i in xrange(h)]
cols = [[0,i] for i in xrange(w)]
bomb_dict = dict()
for i in xrange(m):
    hi,wi = (int(x)-1 for x in input().split())
    rows[hi][0] += 1
    cols[wi][0] += 1
    bomb_dict[(hi,wi)] = True

rows = sorted(rows, reverse=True)
cols = sorted(cols, reverse=True)
row_val = rows[0][0]
col_val = cols[0][0]
ans = None
for row in rows:
    if row[0] != row_val:
        break
    for col in cols:
        if col[0] != col_val:
            break
        getr = bomb_dict.get((row[1], col[1]), False)
        if not getr:
            ans = row_val + col_val
            break
    
    if ans:
        break

if ans is None:
    ans = row_val + col_val - 1
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

h,w,m = (int(x) for x in input().split())
rows = [[0,i] for i in xrange(h)]
cols = [[0,i] for i in xrange(w)]
bomb_dict = dict()
for i in xrange(m):
    hi,wi = (int(x)-1 for x in input().split())
    rows[hi][0] += 1
    cols[wi][0] += 1
    bomb_dict[(hi,wi)] = True

rows = sorted(rows, reverse=True)
cols = sorted(cols, reverse=True)
# print(cols)
ans = 1
for row in rows:
    ans_ans = None
    for col in cols:
        getr = bomb_dict.get((row[1], col[1]), False)
        if getr and ans_ans is None:
            ans_ans = row[0] + col[0] - 1
            # print("1",row[0],col[0], -1)
            best_ans = ans_ans
        elif getr and row[0] + col[0]-1 < ans_ans:
            best_ans = ans_ans
            break
        elif getr:
            pass
        else:
            if ans_ans is None:
                best_ans = row[0] + col[0]
                # print("2",row,col, best_ans)
            else:
                best_ans = max(row[0] + col[0], ans_ans)
                # print("3",row[0],col[0])
            break
    if best_ans > ans:
        ans = best_ans
    if best_ans < ans:
        break
    
print(ans)

Submission status: Accepted

Solution code:
import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

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

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
            # 即座に探索を終了する. これによりループの回数は最大でもM+1回となる.
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)

Submission status: Accepted

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


vert = [0] * (2*W)

def update(i, d):
	i += W
	vert[i] += d
	while i > 1:
		i >>= 1
		vert[i] = max(vert[i*2], vert[i*2+1])


lines = [[] for _ in range(H)]
for _ in range(M):
	y, x = map(lambda s: int(s)-1, input().split())
	lines[y].append(x)
	update(x, 1)

best = 0

for l in lines:
	for x in l: update(x, -1)
	best = max(best, len(l) + vert[1])
	for x in l: update(x, 1)

print(best)