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: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right, insort_right


class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/14718760
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/14705333
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7488469
    # 検証4 (add, __getitem__) [CF] Optimal Subsequences (Hard Version): https://codeforces.com/contest/1261/submission/65643461
    # 検証5 (init, add, pop) Dinner Planning: https://atcoder.jp/contests/code-festival-2018-final-open/submissions/13916065
    # 検証6 (要素がタプル, init, add, remove, max, pop_max) Lake: https://atcoder.jp/contests/snuke21/submissions/14718529
    # 検証7 (init, add, remove, pop, max, pop_max) ドーナツの箱詰め: https://atcoder.jp/contests/donuts-2015/submissions/14829916
    # 検証8 (init, add, remove, min, max) Smart Infants: https://atcoder.jp/contests/abc170/submissions/15264112
    def __init__(self, values=None, sorted_=False, square=1000, seed=42, inf=float("inf")):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        # inf: 番兵（要素がタプルのときは (float("inf"), float("inf")) にする）
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  # 要素の追加  # O(sqrt(n))
        # xorshift
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1 + 1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、x 以上の最小の要素が削除される
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1 + 1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return self.layer1[idx1 - 1]
        return layer0_idx1[idx0 - 1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s == idx:
            layer0[i] += layer0.pop(i + 1)
            return self.layer1.pop(i)
        else:
            return layer0[i].pop(idx - s)

    def pop_max(self):
        # 最大値を削除してその要素を返す（0-indexed） O(1)
        # 空ならエラー
        if self.layer0[-1]:
            return self.layer0[-1].pop()
        else:
            del self.layer0[-1]
            return self.layer1.pop(-2)

    def __getitem__(self, item):
        # 小さい方から idx 番目の要素を返す  O(sqrt(N))
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= item:
                break
        if s == item:
            return self.layer1[i]
        else:
            return layer0[i][item - s]

    def min(self):  # 最小値を返す  空なら inf を返す  O(1)
        return self.layer0[0][0] if self.layer0[0] else self.layer1[0]

    def max(self):  # 最大値を返す  空ならエラー  O(1)
        return self.layer0[-1][-1] if self.layer0[-1] else self.layer1[-2]

    def merge(self, r):  # 結合  O(sqrt(n))
        self.layer0[-1] += r.layer0[0]
        self.layer0 += r.layer0[1:]
        del self.layer1[-1]
        self.layer1 += r.layer1

    def split(self, k):  # k 以上を切り離す  O(sqrt(n))
        idx1 = bisect_left(self.layer1, k)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, k)
        r = SquareSkipList(square=self.square, seed=self.rand_y)
        r.layer1 = self.layer1[idx1:]
        r.layer0 = [layer0_idx1[idx0:]] + self.layer0[idx1 + 1:]
        del self.layer1[idx1:-1], layer0_idx1[idx0:], self.layer0[idx1 + 1:]
        return r

    def print(self):
        print(self.layer1)
        print(self.layer0)

    def __iter__(self):
        layer1 = self.layer1
        layer0 = self.layer0
        idx1 = idx0 = 0
        layer0_idx1 = layer0[idx1]
        while True:
            if len(layer0_idx1) == idx0:
                if len(layer1) - 1 == idx1:
                    return
                yield layer1[idx1]
                idx1 += 1
                layer0_idx1 = layer0[idx1]
                idx0 = 0
            else:
                yield layer0_idx1[idx0]
                idx0 += 1


import sys
from operator import itemgetter
from itertools import groupby
def main():
    H, W, M = map(int, sys.stdin.buffer.readline().split())
    hw = map(int, sys.stdin.buffer.read().split())
    hw = sorted(zip(hw, hw), key=itemgetter(0))
    Cnt_w = [0] * (W+1)
    for _, w in hw:
        Cnt_w[w] += 1
    sl = SquareSkipList([(cnt, w) for w, cnt in enumerate(Cnt_w)], inf=(1<<60, 1<<60))
    ans = 0
    for h, group in groupby(hw, key=itemgetter(0)):
        group = list(group)
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove((cnt, w))
            sl.add((cnt-1, w))
            Cnt_w[w] -= 1
        an = len(group) + sl.max()[0]
        if ans < an:
            ans = an
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove((cnt, w))
            sl.add((cnt+1, w))
            Cnt_w[w] += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

r,c,n = Ri()
row = [0]*r;col = [0]*c
s = set()
for i in range(n):
    temp = Ri()
    temp[0]-=1;temp[1]-=1
    s.add(tuple(temp))
    row[temp[0]]+=1;col[temp[1]]+=1

maxx = -1
for i in range(r):
    for j in range(c):
        maxx = max(maxx, row[i]+col[j]- (1 if (i,j) in s else 0 ))

print(maxx)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=[int(i) for i in raw_input().split()]
r=[0 for i in range(h)]

c=[0 for i in range(w)]
d={}
for i in range(m):
    h1,w1=[int(i)-1 for i in raw_input().split()]
    r[h1]+=1
    c[w1]+=1
    x=str(h1)+"#"+str(w1)
    d[x]=d.get(x,0)+1
maxx=0
for i in range(h):
    for j in range(w):
        x=str(i)+"#"+str(j)
        maxx=max(maxx,r[i]+c[j]-d.get(x,0))
print maxx

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    H, W, M = map(int, input().split())
    h = [0] * H
    w = [0] * W
    hw = set()
    for i in range(M):
        tmph, tmpw = map(lambda x: int(x)-1, input().split())
        h[tmph] += 1
        w[tmpw] += 1
        hw.add((tmph,tmpw))
    # 最大値より1だけ小さくなる物が候補
    HMAX = max(h)
    hcandidate = []
    for i in range(H):
        if h[i] >= HMAX-1:
            hcandidate.append(i)

    WMAX = max(w)
    wcandidate = []
    for i in range(W):
        if w[i] >= WMAX-1:
            wcandidate.append(i)

    ans = 0
    for i in hcandidate:
        for j in wcandidate:
            res = h[i]+w[j]
            if (i,j) in hw:
                res -= 1
            ans = max(ans, res)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hw = [list(map(int, input().split())) for i in range(m)]
ht = [0] * h
wt = [0] * w
for i in hw:
    ht[i[0]-1] += 1
    wt[i[1]-1] += 1
ans = 0
for i in range(h):
    for j in range(w):
        if [i+1, j+1] in hw:
            ans = max(ans, ht[i]+wt[j]-1)
        else:
            ans = max(ans, ht[i]+wt[j])
print(ans)

Submission status: Accepted

Solution code:
def A():
    n, x, t = map(int, input().split())
    print(t * ((n+x-1)//x))

def B():
    n = list(input())
    s = 0
    for e in n:
        s += int(e)
    print("Yes" if s % 9 == 0 else "No")

def C():
    int(input())
    a = list(map(int, input().split()))
    l = 0
    ans = 0
    for e in a:
        if e < l: ans += l - e
        l = max(l, e)
    print(ans)

def E():
    h, w, m = map(int, input().split())
    row = [0] * h
    col = [0] * w
    exist = set([])
    th = 1000000000
    for i in range(m):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        row[x] += 1
        col[y] += 1
        exist.add(x*th + y)

    max_row = max(row)
    max_col = max(col)
    candi_row = []
    candi_col = []
    for i in range(h):
        if row[i] == max_row: candi_row.append(i)
    for i in range(w):
        if col[i] == max_col: candi_col.append(i)

    ans = max_row + max_col
    for x in candi_row:
        for y in candi_col:
            if x*th + y in exist: continue
            print(ans)
            return
    print(ans - 1)

E()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
def main():
    h, w, m = map(int, input().split())
    b_row = [0] * h
    b_col = [0] * w
    b_coor = set()
    m = map(int, read().split())
    for a, b in zip(m, m):
        a -= 1
        b -= 1
        b_row[a] += 1
        b_col[b] += 1
        b_coor.add((a, b))

    row_max = max(b_row)
    col_max = max(b_col)
    rows = [i for i, v in enumerate(b_row) if v == row_max]
    cols = [i for i, v in enumerate(b_col) if v == col_max]

    for r in rows:
        for c in cols:
            if (r, c) not in b_coor:
                print(row_max + col_max)
                sys.exit()
    print(row_max + col_max - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
row=[0]*h
col=[0]*w
s=[]
for _ in range(m):
	x,y=map(int,input().split())
	row[x-1]+=1
	col[y-1]+=1
	s.append([x-1,y-1])
a,b=max(row),max(col)
aa=row.count(a)
bb=col.count(b)
c=0
for x,y in s:
	if row[x]==a and col[y]==b:c+=1
if c<aa*bb:print(a+b)
else:print(a+b-1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

row_bom_cnt = defaultdict(int)
col_bom_cnt = defaultdict(int)
row_max = 0
col_max = 0

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

for rm, cm in boms:
    row_bom_cnt[rm] += 1
    col_bom_cnt[cm] += 1

    row_max = max(row_max, row_bom_cnt[rm])
    col_max = max(col_max, col_bom_cnt[cm])


target_row = set()
for r, val in row_bom_cnt.items():
    if val == row_max:
        target_row.add(r)

target_col = set()
for c, val in col_bom_cnt.items():
    if val == col_max:
        target_col.add(c)


cnt = 0
for rm, cm in boms:
    if rm in target_row and cm in target_col:
        cnt += 1

if len(target_row) * len(target_col) == cnt:
    print(row_max + col_max - 1)
else:
    print(row_max + col_max)

Submission status: Accepted

Solution code:
import itertools
H,W,N=[int(s) for s in input().split()]
hls=[0 for _ in range(H+1)]
wls=[0 for _ in range(W+1)]
bombs=[set() for _ in range(H+1)]
for _ in range(N):
  h,w=[int(s) for s in input().split()]
  hls[h]+=1
  wls[w]+=1
  bombs[h].add(w)
hmax=max(hls)
wmax=max(wls)
hmaxls=[i for i in range(H+1) if hls[i]==hmax]
wmaxls=[i for i in range(W+1) if wls[i]==wmax]
for h,w in itertools.product(hmaxls,wmaxls):
  if not(w in bombs[h]):
    print(hmax+wmax)
    exit()
else:
  print(hmax+wmax-1)

Submission status: Accepted

Solution code:
import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
if h != 1:
  s = 1
  while s < h and h_lst[s][0] == Max_h:
    h_ans.append(h_lst[s][1])
    s+= 1  
if w!= 1:  
  t=1  
  while t < w and w_lst[t][0] == Max_w:
    w_ans.append(w_lst[t][1])
    t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
 
 
def main():
    H, W, M = map(int, sys.stdin.readline().rstrip().split())
    Mh = [0] * H
    Mw = [0] * W
    B = []
    for i in range(M):
        h, w = map(int, sys.stdin.readline().rstrip().split())
        Mh[h - 1] += 1
        Mw[w - 1] += 1
        B.append((h - 1, w - 1))
 
    nh = max(Mh)
    nw = max(Mw)
 
    # 交差する場所に置かれた処理物があるか？
    lh = Counter(Mh)[nh]
    lw = Counter(Mw)[nw]
 
    out = 0
    for (h, w) in B:
        if Mh[h] == nh and Mw[w] == nw:
            out += 1
 
    if out == lh * lw:
        print(nh + nw - 1)
    else:
        print(nh + nw)
 
 
main()

Submission status: Accepted

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

hb = defaultdict(int)
wb = defaultdict(int)
bomb = defaultdict(int)

for hwi in hw:
    h, w = hwi
    hb[h] += 1
    wb[w] += 1
    bomb[(h, w)] += 1

# print(hb, wb)

mhb = max(hb.values())
mwb = max(wb.values())

maxh = [key for key, val in hb.items() if val == mhb]
maxw = [key for key, val in wb.items() if val == mwb]

# print(maxh, maxw)

for h in maxh:
    for w in maxw:
        if bomb[(h, w)] == 0:
            print(mhb + mwb)
            exit()
print(mhb + mwb - 1)

Submission status: Accepted

Solution code:
from collections import Counter
H, W, M = list(map(int, input().split()))
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = list(map(int, input().split()))
hc = Counter(h)
wc = Counter(w)
hmax = max(hc.values())
wmax = max(wc.values())
lh = {k[0] for k in hc.items() if k[1] == hmax}
lw = {k[0] for k in wc.items() if k[1] == wmax}

ct = 0
for i in range(M):
    if h[i] in lh and w[i] in lw:
        ct += 1
if ct >= len(lh)*len(lw):
    print(hmax+wmax-1)
else:
    print(hmax+wmax)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

rows = [0] * (H + 1)
cols = [0] * (W + 1)

from collections import defaultdict
ng_cols = defaultdict(set)

for _ in range(M):
    h, w = map(int, input().split())
    rows[h] += 1
    cols[w] += 1
    ng_cols[h].add(w)

max_of_rows = max(rows)
max_of_cols = max(cols)
max_rows_index = set()
max_cols_index = set()
for i in range(H + 1):
    if rows[i] == max_of_rows:
        max_rows_index.add(i)
for i in range(W + 1):
    if cols[i] == max_of_cols:
        max_cols_index.add(i)
flag = 0
for i in max_rows_index:
    cnt = 0
    for j in ng_cols[i]:
        if j in max_cols_index:
            cnt += 1
    if cnt < len(max_cols_index):
        flag += 1
        break
        
print(max_of_rows + max_of_cols - 1 + flag)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

rows = [0] * (H + 1)
cols = [0] * (W + 1)

from collections import defaultdict
ng_cols = defaultdict(set)

for _ in range(M):
    h, w = map(int, input().split())
    rows[h] += 1
    cols[w] += 1
    ng_cols[h].add(w)

max_of_rows = max(rows)
max_of_cols = max(cols)
max_rows_index = set()
max_cols_index = set()
for i in range(H + 1):
    if rows[i] == max_of_rows:
        max_rows_index.add(i)
for i in range(W + 1):
    if cols[i] == max_of_cols:
        max_cols_index.add(i)
flag = 0
for i in max_rows_index:
    for j in max_cols_index:
        if j not in ng_cols[i]:
            flag = 1
            break
print(max_of_rows + max_of_cols - 1 + flag)

Submission status: Accepted

Solution code:
h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
h_max = max(h_list)
w_max = max(w_list)
w_flag = [0 for _ in range(w)]
for i in range(w):
    if w_list[i] == w_max:
        w_flag[i] = 1
h_flag = [0 for _ in range(h)]
for i in range(h):
    if h_list[i] == h_max:
        h_flag[i] = 1
flag = 0   
for i in range(m):
    if h_flag[a_list[i][0] - 1] == 1 and w_flag[a_list[i][1] - 1] == 1:
        flag += 1
s = sum(h_flag) * sum(w_flag)
print(h_max + w_max - 1 if flag == s else h_max + w_max)

Submission status: Accepted

Solution code:
h,w,m = map(int,input().split())
x = {}
y = {}
dic = {}
for _ in range(m):
    a,b = map(int,input().split())
    dic[(a,b)] = 1
    x[a] = x.get(a,0) + 1
    y[b] = y.get(b,0) + 1
p = max(x.values())
q = max(y.values())
cnt = 1
a = [i for i in x if x[i] == p]
b = [j for j in y if y[j] == q]
for i in a:
    for j in b:
        if dic.get((i,j),-1) == -1:
            cnt = 0
            break
    if not cnt:
        break
print(p+q-cnt)

Submission status: Accepted

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

hlist = [0]*(H+1)
wlist = [0]*(W+1)
for l in L:
    hlist[l[0]] += 1
    wlist[l[1]] += 1

hmax = max(hlist)
wmax = max(wlist)
h = hlist.count(hmax)
w = wlist.count(wmax)
ans = hmax+wmax-1
cnt = 0
for l in L:
    if hlist[l[0]] == hmax and wlist[l[1]] == wmax:
        cnt += 1

if cnt < h*w:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import collections

input = stdin.readline

Y, X, M = map(int, input().split())
bomb = set([tuple(map(int,inp.split())) for inp in stdin.read().splitlines()])
cx = collections.defaultdict(int)
cy = collections.defaultdict(int)
for y,x in bomb:
    cx[x] += 1
    cy[y] += 1
mx = max(cx.values())
my = max(cy.values())
candidateX = [x for (x,v) in cx.items() if v == mx]
candidateY = [y for (y,v) in cy.items() if v == my]
res = mx + my -1
for x in candidateX:
    for y in candidateY:
        if (y,x) not in bomb:
            res += 1
            break
    else:
        continue
    break
print(res)

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())
  hs[h-1] += 1
  ws[w-1] += 1
  s.add((h-1,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:
import sys
input = sys.stdin.readline
h,w,m = map(int,input().rstrip().split())
hw = [list(map(int,input().rstrip().split()))for _ in range(m)]

tate = [0]*(h+1)
yoko = [0]*(w+1)
bombpoint = set()

for x,y in hw:
    tate[x] += 1
    yoko[y] += 1
    bombpoint.add((x,y))

ans_x = []
ans_y = []
x_max = max(tate)
y_max = max(yoko)
for i in range(len(tate)):
    if tate[i] == x_max:
        ans_x.append(i)
for i in range(len(yoko)):
    if yoko[i] == y_max:
        ans_y.append(i)

ans = x_max + y_max
for x in ans_x:
    for y in ans_y:
        if (x,y) not in bombpoint:
            print(ans)
            exit()
print(ans - 1)

Submission status: Accepted

Solution code:
def main():

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

    hmax = max(h_dic)
    wmax = max(w_dic)

    h_maxs = [idx for idx, v in enumerate(h_dic) if v==hmax]
    w_maxs = [idx for idx, v in enumerate(w_dic) if v==wmax]

    # 爆弾数はたかだか3*10~5なので、総当りで解ける
    for h in h_maxs:
        for w in w_maxs:
            if (h, w) not in boms:
                print(hmax + wmax)
                return
    print(hmax + wmax - 1)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import numpy as np

H, W, M = map(int, input().split())
#map_ = np.zeros((H, W), dtype=np.bool)

h_sum = [0] * H
w_sum = [0] * W
point_list = set()

for _ in range(M):
    h, w = map(int, input().split())
    # map_[h-1, w-1] = 1
    point_list.add((h-1, w-1))
    h_sum[h-1] += 1
    w_sum[w-1] += 1

h_max = max(h_sum)
w_max = max(w_sum)

h_argmax = set()
w_argmax = set()

for i, h in enumerate(h_sum):
    if h == h_max:
        h_argmax.add(i) 

for i, w in enumerate(w_sum):
    if w == w_max:
        w_argmax.add(i)

ans = h_max + w_max

for h in h_argmax:
    for w in w_argmax:
        if (h, w) not in point_list:
        # if map_[h, w] == 0:
            print(ans)
            exit()
print(ans - 1)

Submission status: Accepted

Solution code:
h,w,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
H=[0]*h
W=[0]*w
for i in range(m):
  H[l[i][0]-1]+=1
  W[l[i][1]-1]+=1
hmax=max(H)
wmax=max(W)
cthmax=0
ctwmax=0
for i in range(h):
  if H[i]==hmax:
    cthmax+=1
for i in range(w):
  if W[i]==wmax:
    ctwmax+=1
ct=0
for i in range(m):
  if H[l[i][0]-1]==hmax and W[l[i][1]-1]==wmax:
    ct+=1
if cthmax*ctwmax>ct:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read

if sys.argv[-1] == 'ONLINE_JUDGE':
	from numba.pycc import CC
	cc = CC('unko')

	@cc.export('solve', '(i4[:],)')
	def solve(stdin):
		h, w, m = stdin[:3]

		row = np.zeros(h, np.int32)
		col = np.zeros(w, np.int32)
		for i in range(3, m * 2 + 3, 2):
			y, x = stdin[i: i + 2] - 1
			row[y] += 1
			col[x] += 1

		max_cnt_y = max(row)
		max_cnt_x = max(col)
		max_pair = np.sum(row == max_cnt_y) * np.sum(col == max_cnt_x)
		for i in range(3, m * 2 + 3, 2):
			y, x = stdin[i: i + 2] - 1
			if row[y] == max_cnt_y and col[x] == max_cnt_x:
				max_pair -= 1

		return max_cnt_y + max_cnt_x - (max_pair == 0)
	
	cc.compile()
	exit()

from unko import solve
print(solve(np.fromstring(read(), dtype=np.int32, sep=' ')))

Submission status: Accepted

Solution code:
import numpy as np
import sys
from numba import njit, i4
read = sys.stdin.read

@njit((i4[:],), cache=True)
def solve(stdin):
	h, w, m = stdin[:3]

	row = np.zeros(h, np.int32)
	col = np.zeros(w, np.int32)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		row[y] += 1
		col[x] += 1

	max_cnt_y = max(row)
	max_cnt_x = max(col)
	max_pair = np.sum(row == max_cnt_y) * np.sum(col == max_cnt_x)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		if row[y] == max_cnt_y and col[x] == max_cnt_x:
			max_pair -= 1

	return max_cnt_y + max_cnt_x - (max_pair == 0)

print(solve(np.fromstring(read(), dtype=np.int32, sep=' ')))

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read

def solve(stdin):
	h, w, m = stdin[:3]

	row = np.zeros(h, np.int)
	col = np.zeros(w, np.int)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		row[y] += 1
		col[x] += 1

	max_cnt_y = max(row)
	max_cnt_x = max(col)
	max_pair = np.sum(row == max_cnt_y) * np.sum(col == max_cnt_x)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		if row[y] == max_cnt_y and col[x] == max_cnt_x:
			max_pair -= 1

	return max_cnt_y + max_cnt_x - (max_pair == 0)

print(solve(np.fromstring(read(), dtype=np.int, sep=' ')))

Submission status: Accepted

Solution code:
import numpy as np
h, w, m = map(int, input().split())
xy = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
row = np.zeros(h, np.int)
col = np.zeros(w, np.int)
for y, x in xy:
	row[y] += 1
	col[x] += 1

max_cnt_y = max(row)
max_cnt_x = max(col)
max_pair = np.sum(row == max_cnt_y) * np.sum(col == max_cnt_x)
for y, x in xy:
	if row[y] == max_cnt_y and col[x] == max_cnt_x:
		max_pair -= 1

print(max_cnt_y + max_cnt_x - (max_pair == 0))