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:
H, W, M = map(int, input().split())

HB = [0] * H
WB = [0] * W

place = []

for i in range(M):
    h, w = map(int, input().split())
    place.append((h, w,))

    HB[h - 1] += 1
    WB[w - 1] += 1

HBC = [i for i, x in enumerate(HB) if x == max(HB)]
WBC = [i for i, x in enumerate(WB) if x == max(WB)]
result = max(HB) + max(WB)

sw = False
for i in HBC:
    for j in WBC:
        if (i + 1, j + 1,) not in place:
            sw = True
            break
    
    if sw:
        break

if not sw:
    result -= 1

print(result)

Submission status: Time Limit Exceeded

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

h = [0] * H
w = [0] * W

hw = []

for _ in range(M):
    a,b = list(map(int,input().split()))
    h[a - 1] += 1
    w[b - 1] += 1
    hw.append([a,b])

hp = [i for i, v in enumerate(h) if v == max(h)]
wp = [i for i, v in enumerate(w) if v == max(w)]

for x in hp:
    for y in wp:
        if [x+1,y+1] in hw:
            pass
        else:
            print(max(h) + max(w))
            exit()
else:
    print(max(h) + max(w) - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
my_input = sys.stdin.readline

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

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


ans = 0
for h in h_targets.keys():
    for w in w_targets.keys():
        ret = h_targets[h] + w_targets[w] - ((h, w) in targets)
        ans = max(ans, ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

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

hl = [0] * H
wl = [0] * W
mem = set()

for h, w in hw :
  hl[h - 1] += 1
  wl[w - 1] += 1
  mem.add((h - 1, w - 1))
  
mh = max(hl)
mw = max(wl)
hs = []
ws = []
for i, y in enumerate(hl) :
  if y == mh :
    hs.append((i, y))
for i, x in enumerate(wl) :
  if x == mw :
    ws.append((i, x))
    
ret = 0
for x, w in ws :
  for y, h in hs :
    if (y, x) in mem :
      ret = max(ret, w + h - 1)
    else :
      ret = max(ret, w + h)
    
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
h,w,m=(int(x) for x in input().split())
a=[[int(x) for x in input().split()] for _ in range(m)]
b=np.array(a).reshape(-1,)
c=Counter(b[0::2]).most_common()
d=Counter(b[1::2]).most_common()

i=0
j=0
while len(c)>i and c[0][1]==c[i][1]:
    while len(d)>j and d[0][1] == d[j][1]:
        if not [c[i][0],d[j][0]] in a:
            print(c[0][1]+d[0][1])
            quit()
        j+=1
    i+=1
    j=0
print(c[0][1]+d[0][1]-1)

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List

# 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: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    maxRowCount = 0
    maxRowIndexList: List[int] = []
    for row in range(H):
        counter = 0
        for item in codList:
            if item[0] == (row + 1):
                counter += 1
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    for column in range(M):
        counter = 0
        for item in codList:
            if item[1] == (column + 1):
                counter += 1
        if counter > maxColumnCount:
            maxColumnCount = counter
            maxColumnIndexList = [column + 1]
        elif counter == maxColumnCount:
            maxColumnIndexList.append(column + 1)

    result = maxRowCount + maxColumnCount
    for row in maxRowIndexList:
        for column in maxColumnIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bom_list = []
h_list = [0] * H
w_list = [0] * W
for i in range(M):
    h, w = map(int, input().split())
    h_list[h - 1] += 1
    w_list[w - 1] += 1
    bom_list.append([h - 1,w - 1])

h_max = max(h_list)
h_idx = [i for i, j in enumerate(h_list) if j == h_max]
w_max = max(w_list)
w_idx = [i for i, j in enumerate(w_list) if j == w_max]

ans = 0
for i in h_idx:
    for j in w_idx:
        tmp = h_list[i] + w_list[j]
        if [i,j] in bom_list:
            tmp -= 1
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:

from itertools import product

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

B = [0] * H
Bt = [0] * W
for h, w in X:
	B[h-1] += 1
	Bt[w-1] += 1

n = 0
for h, w in product(range(H), range(W)):
	tmp = B[h] + Bt[w]
	for Hx, Wx in X:
		if h+1 == Hx and w+1 == Wx:
			tmp -= 1
	n = max(n, tmp)

print(n)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]
tate, yoko = defaultdict(int), defaultdict(int)
grid = [[False] * w for _ in range(h)]
for h, w in hw:
    grid[h-1][w-1] = True
    tate[h] += 1
    yoko[w] += 1
tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_max, yoko_max = tate[0][1], yoko[0][1]
max_tates, max_yokos = [], []
for t in tate:
    if t[1] == tate_max:
        max_tates.append(t)
    else:
        break
for y in yoko:
    if y[1] == yoko_max:
        max_yokos.append(y)
    else:
        break
for ta in max_tates:
    for yo in max_yokos:
        if grid[ta[0]-1][yo[0]-1] == False:
            print(tate_max + yoko_max)
            exit()
print(tate_max + yoko_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hw = [tuple(map(int, input().split())) for _ in range(m)]

hs = [0]*(h+1)
ws = [0]*(w+1)
for x, y in hw:
  hs[x] += 1
  ws[y] += 1

res = 0
for x in [n for n, v in enumerate(hs) if v == max(hs)]:
  for y in [n for n, v in enumerate(ws) if v == max(ws)]:
    if res < hs[x]+ws[y]:
      res = hs[x]+ws[y]
      if (x, y) in hw:
        res -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

h, w, m = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(m)]
H = [i for i, _ in HW]
W = [i for _, i in HW]

hd = defaultdict(int)
wd = defaultdict(int)

for i, j in HW:
  hd[i] += 1
  wd[j] += 1

hd = list(hd.items())
wd = list(wd.items())

hd.sort(key=lambda x: -x[1])
wd.sort(key=lambda x: -x[1])

kouhoh = []
kouhow = []

for i, j in hd:
  if j < hd[0][1]:
    break
  else:
    kouhoh.append(i)

for i, j in wd:
  if j < wd[0][1]:
    break
  else:
    kouhow.append(i)

for i in kouhoh:
  for j in kouhow:
    if [i, j] not in HW:
      ans = hd[0][1] + wd[0][1]
      print(ans)
      exit()

ans = hd[0][1] + wd[0][1] - 1  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,M=mi()


    H_count = [0] * (H+1)
    W_count = [0] * (W+1)
    G = [[False] * (W+1) for _ in range(H+1)]
    for i in range(M):
        h,w=mi()
        H_count[h] += 1
        W_count[w] += 1
        G[h][w] = True
    
    ans = 0
    for h in range(1,H+1):
        for w in range(1,W+1):
            res = H_count[h] + W_count[w]
            if G[h][w]:
                res -= 1
            ans = max(res,ans)
            # print((h,w),res)


    print(ans)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, M, BOMs):
    h_count = [[0, i] for i in range(H + 1)]
    w_count = [[0, i] for i in range(W + 1)]
    bom_map_h = [[] for i in range(H + 1)]
    for bom in BOMs:
        h_count[bom[0]][0] += 1
        w_count[bom[1]][0] += 1
        bom_map_h[bom[0]].append(bom[1])
    h_count.sort(reverse=True)
    w_count.sort(reverse=True)
    h_max = h_count[0][0]
    w_max = w_count[0][0]
    ans = h_max + w_max - 1
    flg = False
    for hc in h_count:
        if hc[0] < h_max:
            break
        for wc in w_count:
            if wc[0] < w_max:
                break
            if not wc[1] in bom_map_h[hc[1]]:
                ans = h_max + w_max
                flg = True
                break
        if flg:
            break
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    H, W, M = map(int, input().split())
    BOMs = [[int(i) for i in input().split()] for _ in range(M)]
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(H, W, M, BOMs)

Submission status: Time Limit Exceeded

Solution code:

H,W,M=map(int,input().split())
height=[0]*H
width=[0]*W
bomb=[0]*M
bset=set()
for k in range(M):
    bomb[k]=[0]*2
for j in range(M):
    h,w=map(int,input().split())
    bset.add((h-1,w-1))
    bomb[j][0]=h-1
    bomb[j][1]=w-1
    height[h-1]+=1
    width[w-1]+=1
ans=0
#print(bomb)
#print(height)
#print(width)
hmax=max(height)
wmax=max(width)
flag=0
for i in range(H):
    if height[i]==hmax:
        for h in range(W):
            if width[h]==wmax:
                if (i,h) not in bset:
                    flag=1
                    break
if flag==1:
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Time Limit Exceeded

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

hw = []
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw.append(str(h-1)+"_"+str(w-1))

hmax = []
wmax = []
for i, h in enumerate(Hsum):
  if h == max(Hsum):
  	hmax.append(i)
for i, w in enumerate(Wsum):
  if w == max(Wsum):
  	wmax.append(i)
res = []
for h in hmax:
  for w in wmax:
    if str(h)+"_"+str(w) in hw:
      res.append(Hsum[h] + Wsum[w] - 1)
    else:
      res.append(Hsum[h] + Wsum[w])
print(max(res))

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

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

dic_h = Counter(h)
dic_w = Counter(w)

# print(dic_h, dic_w)
max_h_key = max(dic_h.items(), key=lambda x:x[1])[0]
max_w_key = max(dic_w.items(), key=lambda x:x[1])[0]

max_h = dic_h[max_h_key]
max_w = dic_w[max_w_key]
# print(max_h_key, max_w_key, max_h, max_w)

def get_num(ind_h, ind_w):
    ret = 0
    for i in range(M):
        if h[i] == ind_h or w[i] == ind_w:
           ret += 1
    return ret


ans = 0
for ind_h in dic_h.keys():
    if dic_h[ind_h] < max_h:
        continue
    for ind_w in dic_w.keys():
        if dic_w[ind_w] < max_w:
            continue
        ret = get_num(ind_h, ind_w)
        ans = max(ans, ret)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=[]
mwi=[]
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]

for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
  
  #ans[a][b]+=1

for i in mhi:
  for j in mwi:
    if [i+1, j+1] in s:
      continue
    print(mh+mw)
    quit()
print(mh+mw-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

h_count = {}
w_count = {}
for h,w in hw:
    if h in h_count:
        h_count[h] += 1
    else:
        h_count[h] = 1
    if w in w_count:
        w_count[w] += 1
    else:
        w_count[w] = 1

max_h = max(h_count.values())
max_w = max(w_count.values())
ans = max_h + max_w

max_h_list = [k for k,v in h_count.items() if v == max_h]
max_w_list = [k for k,v in w_count.items() if v == max_w]

for h in max_h_list:
    for w in max_w_list:
        if [h, w] not in hw:
            print(ans)
            sys.exit()
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
dich = {}
dicw = {}

havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1

dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])

# print(havew)
#
# print(dichi)
# print(dicwi)

hmax = dichi[0][1]
wmax = dicwi[0][1]

for hs in dichi:
    if hs[1] != hmax:
        break
    for ws in dicwi:
        if ws[1] != wmax:
            break
        if ws[0] not in havew[hs[0]]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=set()
for i in range(m):
  h1,w1=input().split()
  l.add(h1+"_"+w1)
  lh[int(h1)-1]+=1
  lw[int(w1)-1]+=1

hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    lw2.append(i)

s=1
for m in lh2:
  for m2 in lw2:
    if str(m+1)+"_"+str(m2+1) not in l:
      s=0
      
print(hmax+wmax-s)

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:
import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = {}
H = {}
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    if not h in H:
        H[h] = 1
    else:
        H[h] += 1
    
    if not w in W:
        W[w] = 1
    else:
        W[w] += 1

    HW[h][w] = 1
answer = 0
HMAXES = []
WMAXES = []
HMAX = max(H.values())
WMAX = max(W.values())

for ki, vi in H.items():
    if vi == max(H.values()):
        HMAXES.append(ki)
for ki, vi in W.items():
    if vi == max(W.values()):
        WMAXES.append(ki)

answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = [i for i in range(300001) if x[i] == mx]
y1 = [i for i in range(300001) if y[i] == my]
z1 = list(itertools.product(x1, y1))
if set(z) >= set(z1): print(mx + my - 1)
else: print(mx + my)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
#n = int(input())
h, w, m = map(int, sys.stdin.readline().split())
#n = input()
#a = list(map(int, sys.stdin.readline().split()))

ver = [0 for i in range(w)]
par = [0 for i in range(h)]
b = [[0 for i in range(w)] for j in range(h)]

for i in range(m):
    H, W = map(int, sys.stdin.readline().split())
    b[H-1][W-1] = 1
    par[H-1] += 1
    ver[W-1] += 1

mp = max(par)
mplist = [i for i, x in enumerate(par) if x == mp]
mv = max(ver)
mvlist = [i for i, x in enumerate(ver) if x == mv]

flag = 1
for i in range(len(mplist)):
    for j in range(len(mvlist)):
        if b[mplist[i]][mvlist[j]] == 0:
            flag = 0
            break

print(mp + mv - flag)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict

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

    retu = Counter()
    gyo = Counter()

    ipt = defaultdict(list)

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].append(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
from collections import defaultdict
h, w, m = map(int,input().split())
row = defaultdict(int)
col = defaultdict(int)
grid = defaultdict(int)
for _ in range(m):
    x,y = map(int,input().split())
    row[x]+=1
    col[y]+=1
    grid[(x,y)]+=1

maxi = 0
for i in row:
    for j in col:
        if maxi<row[i]+col[j]:
            maxi = row[i]+col[j]
            if grid[(i,j)]:
                maxi-=1
print(maxi)

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])
from collections import deque
ans_x=deque()
ans_y=deque()
x=0
y=0
for i in range(1,h+1):
    if h_[i]>x:
        x=h_[i]
        ans_x=deque()
        ans_x.append(i)
    elif h_[i]==x:
        x=h_[i]
        ans_x.append(i)    
for j in range(1,w+1):
    if w_[j]>y:
        y=w_[j]
        ans_y=deque()
        ans_y.append(j)
    elif w_[j]==y:
        y=w_[j]
        ans_y.append(j)
ans=x+y
ans_x=list(ans_x)
ans_y=list(ans_y)
u=0
c=0
for i in ans_x:
    for j in ans_y:
        if [i,j] in plot:
            u+=1
        c+=1
if c==u:
    print(ans-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
import itertools

def solve(ah, aw, s: set):
    ahh, ahc = ah
    aww, awc = aw
    if (ahh, aww) in s:
        return ahc+awc-1
    else:
        return ahc + awc

def main():
    H, W, M = map(int, input().split())
    LH = []
    LM = []
    s = set()
    for _ in range(M):
        h, w = map(int, input().split())
        LH.append(h)
        LM.append(w)
        s.add((h,w))
    
    ch = Counter(LH)
    cm = Counter(LM)

    ah = ch.most_common()
    aw = cm.most_common()
    th = ah[0][1]
    tw = aw[0][1]
    #print("t=", th + tw)
    ah = [x for x in ah if x[1]==th]
    aw = [x for x in aw if x[1]==tw]
    ans = 0
    for x, y in itertools.product(ah, aw):
        ans = max(ans, solve(x, y, s))
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
H,W,M = list(map(int, input().split()))

hw = [[0] * W for _ in range(H)]
hw = np.array(hw)

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

a = 0
for i in range(H):
    h = np.sum(hw[i,:])
    for j in range(W):
        w = np.sum(hw[:,j])
        d = hw[i,j]
        a = max(a, h+w-d)
print(a)

Submission status: Time Limit Exceeded

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

h = [-1]
w = [-1]
hw = []
for _ in range(M):
    hi,wi = map(int,input().split())
    h.append(hi)
    w.append(wi)
    hw.append([hi,wi])
# print(h)
# print(w)
# print(hw)
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
for i in range(1,M+1):
    h_cnt[h[i]]+=1
    w_cnt[w[i]]+=1
# print(h_cnt)
# print(w_cnt)

h_max = max(h_cnt)
w_max = max(w_cnt)

h_max_idx = []
w_max_idx = []

for i in range(1,H+1):
    if h_cnt[i]==h_max:
        h_max_idx.append(i)

for i in range(1,W+1):
    if w_cnt[i]==w_max:
        w_max_idx.append(i)

ans = 0

for i in h_max_idx:
    for j in w_max_idx:
        tmp =  h_cnt[i]+w_cnt[j]
        if [i,j] in hw:
            tmp -=1
        ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[]
for i in range(m):
  h1,w1=map(int,input().split())
  l.append([h1,w1])
  lh[h1-1]+=1
  lw[w1-1]+=1

hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    lw2.append(i)

s=1
for m in lh2:
  for m2 in lw2:
    if [m+1,m2+1] not in l:
      s=0
      
print(hmax+wmax-s)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hs = [0] * h
ws = [0] * w
pos = []
for _ in range(m):
    hi, wi = map(int, input().split())
    pos.append([hi, wi])
    hs[hi-1] += 1
    ws[wi-1] += 1
    
mh = max(hs)
mhs = []
for i in range(h):
    if hs[i] == mh:
        mhs.append(i+1)

mw = max(ws)
mws = []
for i in range(w):
    if ws[i] == mw:
        mws.append(i+1)

flg = False
for i in mhs:
    for j in mws:
        if [i, j] not in pos:
            flg = True
            print(max(hs) + max(ws))
            break
    if flg:
        break
else:
    print(max(hs) + max(ws) - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hwList = []
hList = [0] * (h + 1)
wList = [0] * (w + 1)
for x in range(m):
    h_i, w_i = map(int, input().split())
    hList[h_i] += 1
    wList[w_i] += 1
    hwList.append([h_i, w_i])
h_max = max(hList)
w_max = max(wList)
h_maxid = [i for i, v in enumerate(hList) if v == h_max]
w_maxid = [i for i, v in enumerate(wList) if v == w_max]
isminus = 1
for a in h_maxid:
    for b in w_maxid:
        if [a, b] in hwList: continue
        isminus = 0
print(max(hList) + max(wList) - isminus)

Submission status: Time Limit Exceeded

Solution code:

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

bom = [list(map(int,input().split())) for i in range(M)]
H_sum = [0]*H
W_sum = [0]*W

bom_list = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
    H_sum[bom[i][0]-1] += 1
    W_sum[bom[i][1]-1] += 1
    bom_list[bom[i][0]-1][bom[i][1]-1] = 1

H_max = max(H_sum)
W_max = max(W_sum)

H_list = []
for i in range(H):
    if H_sum[i] == H_max:
        H_list.append(i)

W_list = []
for i in range(W):
    if W_sum[i] == W_max:
        W_list.append(i)

flg = False
for i in H_list:
    for j in W_list:
        if bom_list[i][j] == 0:
            flg = True
            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 = []
for m in range(M):
  bomb.append(tuple(map(int, input().split())))
max_num = 0 
for i in range(1, H+1):
  for j in range(1, W+1):
    tmp = 0
    # 横の要素
    for w in range(1, W+1):
      if (i, w) in bomb:
        tmp += 1
	# 縦の要素
    for h in range(1, H+1):
      if (h, j) in bomb:
        if (h, j) == (i, j):
          continue
        tmp += 1
    if max_num < tmp:
      max_num = tmp
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bomb = [0] * M
H_list = [0] * H
W_list = [0] * W
for i in range(M):
  h, w = map(int, input().split()) 
  bomb[i] = [h - 1, w - 1]
  H_list[h - 1] += 1
  W_list[w - 1] += 1
  
#print(HW, H_list, W_list)  
H_max = max(H_list)
W_max = max(W_list)
H_index = []
W_index = []
for i in range(H):
  if H_list[i] == H_max:
    H_index.append(i)
    
for i in range(W):
  if W_list[i] == W_max:
    W_index.append(i)
    

x = 1
for i in H_index:
  for j in W_index:
    if [i, j] not in bomb:
      x = 0
      
print(H_max + W_max - x)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
p = [[0 for i in range(w)]for i in range(h)]
hlist = [0 for i in range(h)]
wlist = [0 for i in range(w)]
for i in range(m):
    a,b = map(int,input().split())
    hlist[a-1] += 1
    wlist[b-1] += 1
    p[a-1][b-1] = 1
q = 0
for i in range(h):
    q = max(q,hlist[i])
s = []
for i in range(h):
    if hlist[i] == q:
        s.append(i)
r = 0
for i in range(w):
    r = max(r,wlist[i])
t = []
for i in range(w):
    if wlist[i] == r:
        t.append(i)
ans = 0
for i in range(len(s)):
    for j in range(len(t)):
        if p[s[i]][t[j]] == 1:
            pass
        else:
            ans = q+r
            break
if ans == 0:
    print(q+r-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = defaultdict(int)
h_targets = defaultdict(int)
w_targets = defaultdict(int)

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


ans = 0
for h in range(H):
    for w in range(W):
        ret = h_targets[h] + w_targets[w] - targets[(h, w)]
        ans = max(ans, ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

    retu = Counter()
    gyo = Counter()

    ipt = [[] for _ in range(H)]

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].append(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())

Submission status: Time Limit Exceeded

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

for i in range(M):
    L[B[i][0]-1]+=1
    C[B[i][1]-1]+=1

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

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

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

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

Submission status: Time Limit Exceeded

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

H,W,M=map(int,input().split())
B=set([tuple(map(int,input().split())) for i in range(M)])

HH=[0]*(H+1)
WW=[0]*(W+1)

for x,y in B:
    HH[x]+=1
    WW[y]+=1

MAXH=max(HH)
MAXW=max(WW)

ANS=MAXH+MAXW-1

for i in range(1,H+1):
    if HH[i]!=MAXH:
        continue
    for j in range(1,W+1):
        if WW[j]!=MAXW:
            continue

        if (i,j) in B:
            continue
        else:
            print(ANS+1)
            sys.exit()
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
X = [[0 for i in range(w)] for _ in range(h)]
for i in range(m):
    mh, mw = list(map(int, input().split()))
    X[mh-1][mw-1] = 1
    count_row[mh-1] += 1
    count_col[mw-1] += 1
max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
ans = max(count_row) + max(count_col) -1
flag = False
for i in max_row_index:
    for j in max_col_index:
        if X[i][j] == 0:
            ans += 1
            flag = True
            break
    if flag:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
#memo:重なっている位置に爆弾があるかないかで、1こ増減することが考えられる
#import numpy as np

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

tate = [0] * H
yoko = [0] * W


bomb = []
for i in range(M):
    hi, wi = map(int,input().split())
    tate[hi-1] += 1
    yoko[wi-1] += 1
    bomb.append([hi,wi])

#print(tate)
#print(yoko)
#print(bomb)

tate_max = max(tate)
yoko_max = max(yoko)
index_tate = [i for i, v in enumerate(tate) if v == tate_max]
index_yoko = [i for i, v in enumerate(yoko) if v == yoko_max]
#print(index_tate, index_yoko)

dammy = True
#1子でも「そこにない」ものがあれば、そのまま加算、そうでなければ、1こ引く
there_is = True
for i in index_tate:
    for j in index_yoko:
        #print(i+1, j+1)
        if([i+1, j+1] in bomb):
            dammy = True
        else:
            there_is = False

if(there_is):
    print(tate_max + yoko_max - 1)
else:
    print(tate_max + yoko_max)


        




'''
#tate_max = [i for i, v in enumerate(tate) if v == max(tate)]
np_list_tate = np.array(tate)
np_list_yoko = np.array(yoko)
tate_max = np_list_tate.argmax()
yoko_max = np_list_yoko.argmax()
print(tate_max, yoko_max)
'''