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:
import collections

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

ha = [e[0] for e in L]
wa = [e[1] for e in L]
hb = collections.Counter(ha).most_common()
wb = collections.Counter(wa).most_common()
hc = [e for e in hb if e[1] == hb[0][1]]
wc = [e for e in wb if e[1] == wb[0][1]]
hd = [e[0] for e in hc]
wd = [e[0] for e in wc]

flag = False
for he in hd:
    for we in wd:
        if [he, we] not in L:
            flag = True

ans = hb[0][1] + wb[0][1]
if not flag:
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
import itertools

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

F = [[0 for _ in range(W + 1)] for _ in range(H + 1)]

d_h = deque()
d_w = deque()
for h, w in HW:
    d_h.append(h)
    d_w.append(w)
    F[h][w] += 1

# 出現頻度順にソート
c_h = Counter(d_h).most_common()
c_w = Counter(d_w).most_common()

# 登場頻度の一番高い回数
n_h = c_h[0][1]
n_w = c_w[0][1]

# 同率のものを数える
t_h = deque()
t_w = deque()

for k, v in c_h:
    if v == n_h:
        t_h.append(k)
    else:
        break

for k, v in c_w:
    if v == n_w:
        t_w.append(k)
    else:
        break

q = set(list(itertools.product(t_h, t_w)))

for h, w in HW:
    q.discard((h, w))

if len(q) == 0:
    ans = n_h + n_w - 1
else:
    ans = n_h + n_w

print(ans)

Submission status: Time Limit Exceeded

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

nh = [0] * H  # number of h == i+1
nw = [0] * W  # number of w == i+1

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

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

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

hw = list(zip(h, w))
for h1 in mh:
    for w1 in mw:
        if (h1, w1) not in hw:
            print(mnh + mnw)
            exit()
print(mnh + mnw - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

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

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

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

minus = []
for x in h_idx:
    for y in w_idx:
        if (x, y) in boms:
            minus.append(-1)
        else:
            minus.append(0)

print(h_max + w_max + max(minus))

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split(' '))
grid = {}
h_b = set()

h_max = 0
w_max = 0
h_max_grid = 0
w_max_grid = 0

h_b = set()
w_b = set()

for i in range(m):
    hi, wi = map(int, input().split(' '))
    grid[(hi, wi)] = 1
    grid[(hi, 0)] = grid.get((hi, 0), 0) + 1
    grid[(0, wi)] = grid.get((0, wi), 0) + 1

    if h_max < grid[(hi,0)]:
        h_max = grid[(hi,0)]

    if w_max < grid[(0,wi)]:
        w_max = grid[(0,wi)]

    t = h_max + w_max
    h_b.add(hi)
    w_b.add(wi)

flg = False
for hb in list(h_b):
    if grid[(hb, 0)] != h_max:
        continue

    for wb in list(w_b):
        if grid[(0, wb)] != w_max:
            continue
        
        if grid.get((hb, wb), 0) != 1:
            flg = True
            break
    else:
        continue
    break

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

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
bomb_list = []
 
bomb_list = [list(map(int, input().split())) for i in range(m)]
 
for o in range(m):
    for p in range(2):
        bomb_list[o][p] -= 1
 
h_count_list = [0 for j in range(h)]
w_count_list = [0 for k in range(w)]
 
max_h_count = 0
max_w_count = 0
 
x_list = []
y_list = []
 
for l in range(m):
    a = bomb_list[l][0]
    h_count_list[a] += 1
 
max_h_count = max(h_count_list)
 
for c in range(h):
    if h_count_list[c] == max_h_count:
        x_list.append(c)
    
for n in range(m):
    b = bomb_list[n][1]
    w_count_list[b] += 1
 
max_w_count = max(w_count_list)
 
for d in range(w):
    if w_count_list[d] == max_w_count:
        y_list.append(d)
 
e = 0
 
for x in x_list:
    for y in y_list:
        if bomb_list.count([x, y]) == 1 and e <= max_w_count + max_h_count - 1:
            e = max_w_count + max_h_count - 1
        elif e <= max_w_count + max_h_count:
            e = max_w_count + max_h_count
 
print(e)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    chance = h_w_list[h_index][w_index] != 1

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


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

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

h_max = max(ch.values())
w_max = max(cw.values())

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

minus = []
for x in h_idx:
    for y in w_idx:
        if (x, y) in boms:
            minus.append(-1)
        else:
            minus.append(0)

print(h_max + w_max + max(minus))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    chance = h_w_list[h_index][w_index] != 1

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

h_max = max(ch.values())
w_max = max(cw.values())

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

boms = set([(x, y) for x, y in zip(h, w)])

minus = []
for x in h_idx:
    for y in w_idx:
        if (x, y) in boms:
            minus.append(-1)
        else:
            minus.append(0)

print(h_max + w_max + max(minus))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
hw = [map(int, input().split()) for _ in range(M)]
h, w = [list(i) for i in zip(*hw)]

# 爆破対象が1行あたり何個置いてあるかをH行調べる
hl = []*H
for i in range(1,H+1):
  hl.append(h.count(i))


# まず爆破対象が最も多い行を調べて爆破対象の個数を取得
hmax = hl.index(max(hl)) + 1
hcount = h.count(hmax)
#print(h,hmax,hcount)

# hmax行以外の行の爆破対象を調べる
w = [w[i] for i in range(M) if h[i] != hmax]

# 爆破対象の調べ方は行のときと同じ
wl = []*W
for j in range(1,W+1):
  wl.append(w.count(j))

wmax = wl.index(max(wl)) + 1
wcount = w.count(wmax)

# 行と列の合計
print(hcount+wcount)

Submission status: Time Limit Exceeded

Solution code:
import collections

H,W,M = map(int, input().split())
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())
ch = collections.Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = collections.Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
hw = list(zip(h,w))
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in hw:
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
for x in xs:
    for y in ys:
        if (y, x) in points:
            ans = max(ans, count_h[y] + count_w[x] - 1)
        else:
            ans = max(ans, count_h[y] + count_w[x])
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

double_chance = False
# print("---")
for h_index in h_max_indexs:
  if double_chance:
    break
  for w_index in w_max_indexs:
    if double_chance:
      break
    chance = h_w_list[h_index][w_index] != "target"

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
import itertools

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

F = [[0 for _ in range(W + 1)] for _ in range(H + 1)]

d_h = deque()
d_w = deque()
for h, w in HW:
    d_h.append(h)
    d_w.append(w)
    F[h][w] += 1

# 出現頻度順にソート
c_h = Counter(d_h).most_common()
c_w = Counter(d_w).most_common()

# 登場頻度の一番高い回数
n_h = c_h[0][1]
n_w = c_w[0][1]

# 同率のものを数える
t_h = deque()
t_w = deque()

for k, v in c_h:
    if v == n_h:
        t_h.append(k)
    else:
        break

for k, v in c_w:
    if v == n_w:
        t_w.append(k)
    else:
        break


for h, w in itertools.product(t_h, t_w):
    if F[h][w] == 0:
        ans = n_h + n_w
        break
    else:
        continue
else:
    ans = n_h + n_w - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
bo=[]
hb=[0]*h
wb=[0]*w
for i in range(m):
    a,b=list(map(int, input("").split()))
    #各行列に爆弾いくつあるか
    hb[a-1]+=1
    wb[b-1]+=1
    #爆弾の座標
    bo.append([a,b])
#ソート
mwb=[]
mhb=[]
#爆弾数が最大の行と列番号をメモ
hmax=max(hb)
wmax=max(wb)
for i in range(h):
    if hb[i]==hmax:
        mhb.append(i+1)
for i in range(w):
    if wb[i]==wmax:
        mwb.append(i+1)
c=0
#最大の爆弾数の行と列に含まれる爆弾数=cの確認
for h,w in bo:
    if h in mhb and w in mwb:
        c+=1
#行と列の最大爆弾数の和
out=hmax+wmax
#行と列の最大数の積がcと一致するなら必ず重複があるので－1
if c==len(mwb)*len(mhb):
    out-=1
print(out)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
hb= [i for i in range(h)]
wb=[i for i in range(w)]
bo=[]
hb=[0]*h
wb=[0]*w
for i in range(m):
    a,b=list(map(int, input("").split()))
    #各行列に爆弾いくつあるか
    hb[a-1]+=1
    wb[b-1]+=1
    #爆弾の座標
    bo.append([a,b])
#ソート
mwb=[]
mhb=[]
#爆弾数が最大の行と列番号をメモ
hmax=max(hb)
wmax=max(wb)
for i in range(h):
    if hb[i]==hmax:
        mhb.append(i+1)
for i in range(w):
    if wb[i]==wmax:
        mwb.append(i+1)
c=0
#最大の爆弾数の行と列に含まれる爆弾数=cの確認
for h,w in bo:
    if h in mhb and w in mwb:
        c+=1
#行と列の最大爆弾数の和
out=hmax+wmax
#行と列の最大数の積がcと一致するなら必ず重複があるので－1
if c==len(mwb)*len(mhb):
    out-=1
print(out)

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List
import array
import numpy as np

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


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

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList = np.zeros(W, dtype="int32")
    rowSumList = np.zeros(H, dtype="int32")

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

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

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
  
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
 
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す
 
for T in range(M):
  if c[T][0] in leftkeys:
    if c[T][1] in rightkeys:
      cnt = cnt + 1
    else:
      pass
  else:
    pass
 
 
if cnt == int(leftkeyN * rightkeyN):
    print(int(tempmax - 1))
else:
    print(int(tempmax))

Submission status: Time Limit Exceeded

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

hlis=[0 for i in range(h)]
wlis=[0 for i in range(w)]
lis=[[0 for _ in range(w)] for _ in range(h)]

for i in range(m):
  hi,wi=map(int,input().split())
  hlis[hi-1]+=1
  wlis[wi-1]+=1
  lis[hi-1][wi-1]+=1


hmax=max(hlis)
wmax=max(wlis)

ph=[]
pw=[]
for i in range(h):
  if hlis[i]==hmax:
    ph.append(i)
for i in range(w):
  if wlis[i]==wmax:
    pw.append(i)


cvac=0
for phi in ph:
  for pwj in pw:
    if lis[phi][pwj]==0:
      cvac+=1
      break
  if cvac==1:
    break

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  h, w, m = map(int, input().split())
  #graph = np.zeros((h, w), dtype='int64')
  row_sum = np.zeros(h, dtype='int64')
  col_sum = np.zeros(w, dtype='int64')
  pos = []

  for _ in range(m):
    i, j = map(int, input().split())
    #graph[i-1][j-1] = 1
    row_sum[i-1] += 1
    col_sum[j-1] += 1
    pos.append((i-1, j-1))

  #print(row_sum)
  #print(col_sum)

  max_row = max(row_sum)
  max_col = max(col_sum)

  result = max_row+max_col

  ris = np.where(row_sum == max_row)
  cis = np.where(col_sum == max_col)
  
  #print(ris)
  #print(cis)
  #print(pos)

  for ri in ris[0]:
    for ci in cis[0]:
      #if graph[ri][ci] == 0:
      if (ri, ci) not in pos:
        return result
  return result-1
  
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w,m = map(int,input().split())
H = [0]*(h)
W = [0]*(w)
ls = []
for _ in range(m):
    a,b = map(int,input().split())
    ls.append([a-1,b-1])
    H[a-1] += 1
    W[b-1] += 1
hm = max(H)
wm = max(W)
for i in range(len(H)):
    for j in range(len(W)):
        if W[j] == wm and H[i] == hm and [i,j] not in ls:
            print(hm+wm)
            sys.exit()
print(hm+wm-1)

Submission status: Time Limit Exceeded

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

row = [ 0 for _ in range(h)]
col = [ 0 for _ in range(w)]
pos = []

for _ in range(m):
    r, c = map(lambda x: int(x) - 1, input().split())
    row[r] += 1
    col[c] += 1
    pos.append([r, c])

rmax = max(row)
cmax = max(col)

cross_c = 0
rcand = [i for i in range(h) if row[i] == rmax]
ccand = [i for i in range(w) if col[i] == cmax]
for r, c in pos:
    if r in rcand and c in ccand:
        cross_c += 1

if len(rcand) * len(ccand) > cross_c:
    print(rmax + cmax)
else:
    print(rmax + cmax - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=[]
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.append((x,y))
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
ans=x+y-1
c=False
for i in a:
    for j in b:
        if (i,j) not in plot:
          c=True
          break
    if c:
      break
if c:
  print(ans+1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List
import array
import numpy as np

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


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

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: array[int] = np.zeros(W, dtype="int32")
    rowSumList: array[int] = np.zeros(H, dtype="int32")

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

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

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
H = int(l[0])
W = int(l[1])
M = int(l[2])

G = []
for i in range(M):
    x, y = map(int, input().split())
    g = [x, y]
    G.append(g)

h = [0]*H
for i in range(M):
    h[G[i][0]-1] += 1

w = [0]*W
for i in range(M):
    w[G[i][1]-1] += 1

cnt = 0
for i in range(H):
    for j in range(W):
        x = h[i] + w[j]
        if x <= cnt:
            continue
        for k in range(M):
            if G[k] == [i+1, j+1]:
                x -= 1
        if x > cnt:
            cnt = x
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split(' '))
grid = {}
h_b = set()

h_max = 0
w_max = 0
h_max_grid = 0
w_max_grid = 0

h_b = set()
w_b = set()

for i in range(m):
    hi, wi = map(int, input().split(' '))
    grid[(hi, wi)] = 1
    grid[(hi, 0)] = grid.get((hi, 0), 0) + 1
    grid[(0, wi)] = grid.get((0, wi), 0) + 1

    if h_max < grid[(hi,0)]:
        h_max = grid[(hi,0)]

    if w_max < grid[(0,wi)]:
        w_max = grid[(0,wi)]

    t = h_max + w_max
    grid[(0,0)] = t if grid.get((0,0), 0) < t else grid.get((0,0), 0)
    h_b.add(hi)
    w_b.add(wi)

flg = False
for hb in list(h_b):
    if grid[(hb, 0)] != h_max:
        continue

    for wb in list(w_b):
        if grid[(0, wb)] != w_max:
            continue
        
        if grid.get((hb, wb), 0) != 1:
            flg = True
            break
    else:
        continue
    break

if flg:
    print(grid[(0,0)])
else:
    print(grid[(0,0)]-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int,input().split()))
s=[]
t=[]
st=[[] for i in range(h+1)]
for i in range(m):
  H,W=list(map(int,input().split()))
  s.append(H)
  t.append(W)
  st[H].append(W)
from collections import Counter
u=Counter(s)
v=Counter(t)
max_u=max(u.values())
max_v=max(v.values())
import sys
for i in u:
  if u[i]==max_u:
    for j in v:
      if v[j]==max_v:
        if j not in st[i]:
          print(max_u+max_v)
          sys.exit()
      
      
print(max_u+max_v-1)

Submission status: Time Limit Exceeded

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

bombw = [0]*w
bombh = [0]*h
bomb = [""]*m
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    bomb[i] = str(hi-1)+"-"+str(wi-1)
    # print(bomb)
maw = max(bombw)
mah = max(bombh)
# print(maw,mah)
inmaw = [i for i, x in enumerate(bombw) if x == maw]
inmah = [i for i, x in enumerate(bombh) if x == mah]
# print(inmaw,inmah)

ans = maw + mah
# print(bomb)
# print(ans)
for i in inmah:
    for j in inmaw:
        if str(i)+"-"+str(j) not in bomb:
            print(ans)
            exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
A = [0]*H
B = [0]*W
D = set()
for _ in range(M):
    h,w = map(int, input().split())
    A[h-1] += 1
    B[w-1] += 1
    D.add((h-1,w-1))
a, b = max(A), max(B)
res = a+b-1
for i in range(H):
    for j in range(W):
        if (A[i],B[j]) == (a,b):
            if (i,j) not in D:
                print(res+1)
                exit()
print(res)

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int, input().split())
arr = [[0 for _ in range(b)] for _ in range(a)]
for _ in range(c):
    x,y = map(int, input().split())
    arr[x-1][y-1] = '#'

counts = []
new_list = list(zip(*arr))
ans = 0
for k in range(b):
    counts.append(new_list[k].count('#'))
    
for i in range(a):
    temp = arr[i].count('#')
    for j in range(b):
        if arr[i][j] == '#':
            ans = max(ans, temp+counts[j]-1)
        else:
            ans = max(ans, temp+counts[j])
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
smat=[list(map(int,input().split())) for i in range(m)]
hb=[d[0] for d in smat]
wb=[d[1] for d in smat]
cmax1=0
cmax2=0

hpos=[]
hmax=0
for i in range(h):
    hcc=hb.count(i+1)
    if hcc>hmax:
        hmax=hcc
        hpos=[i+1]
    elif hcc==hmax:
        hpos.append(i+1)

wpos=[]
wmax=0
for i in range(w):
    wcc=wb.count(i+1)
    if wcc>wmax:
        wmax=wcc
        wpos=[i+1]
    elif wcc==wmax:
        wpos.append(i+1)

for i in hpos:
    for j in wpos:
        if [i,j] in smat:
            cmax1=hmax+wmax-1
        else:
            cmax2=hmax+wmax
print(max(cmax1,cmax2))

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if not [cand_h[i], cand_w[j]] in object:
            ans = h_max + w_max
            break
            break           
else:
   ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

hl = [l[0] for l in L]
wl = [l[1] for l in L]

ans = 0
hm = collections.Counter(hl).most_common()
wm = collections.Counter(wl).most_common()

hn = [e for e in hm if e[1] == hm[0][1]]
wn = [e for e in wm if e[1] == wm[0][1]]

for he in hn:
    for we in wn:
        h = he[0]
        w = we[0]
        tmp = he[1] + we[1]
        if [h,w] in L:
            tmp -= 1
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max - 1
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(cand_h)):
      for j in range(len(cand_w)):
         if not [cand_h[i], cand_w[j]] in object:
            ans = h_max + w_max            
else:
   ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
ans = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) in m.keys():
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
h, w, m=map(int,input().split())
H=[0]*h
W=[0]*w
HW=[]

for i in range(m) :
    h_, w_=map(int,input().split())
    H[h_-1]+=1
    W[w_-1]+=1
    HW.append([h_-1,w_-1])
    
maxH=max(H)
maxW=max(W)

mh=[i for i,v in enumerate(H) if v==maxH]
mw=[i for i,v in enumerate(W) if v==maxW]

for i in mh :
    for j in mw :
        if [i,j] not in HW :
            print(maxH+maxW)
            sys.exit()
print(maxH+maxW-1)

Submission status: Time Limit Exceeded

Solution code:
l = input().split()
H = int(l[0])
W = int(l[1])
M = int(l[2])

G = []
for i in range(M):
    x, y = map(int, input().split())
    g = [x, y]
    G.append(g)

h = [0]*H
for i in range(H):
    for j in range(M):
        if G[j][0] == i+1:
            h[i] += 1

w = [0]*W
for i in range(W):
    for j in range(M):
        if G[j][1] == i+1:
            w[i] += 1

cnt = 0
for i in range(H):
    for j in range(W):
        x = h[i] + w[j]
        for k in range(M):
            if G[k] == [i+1, j+1]:
                x -= 1
        if x > cnt:
            cnt = x
print(cnt)