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:
# -*- 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
dic_combi = defaultdict(int)

for _ in range(M):
    h_, w_ = map(int, input().split())
    h.append(h_)
    w.append(w_)
    dic_combi[h_ * (10**6) +  w_]=1

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]

keys_h = [k for k, v in dic_h.items() if v == max_h]
keys_w = [k for k, v in dic_w.items() if v == 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 keys_h:
    for ind_w in keys_w:
        # ret = get_num(ind_h, ind_w)
        ret = max_h + max_w
        if dic_combi[ind_h*(10**6) + ind_w] == 1:
            ret -= 1
        ans = max(ans, ret)

print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
A=[]
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

add=1
for i in mh:
    for j in mw:
        #print(hs[i],ws[j])
        if (i,j) not in A:
            add=0
            break


ans-=add

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())
mat = [[0 for i in range(W)] for j in range(H)]
width = [0]*W
height = [0]*H
for i in range(M):
  x,y = map(int, input().split())
  width[y-1] += 1
  height[x-1] += 1
  mat[x-1][y-1] = 1

indexW = [i for i, v in enumerate(width) if v == max(width)]
indexH = [i for i, v in enumerate(height) if v == max(height)]
notHere = False
for i in indexW:
  for j in indexH:
    if mat[j][i] == 0:
      notHere = True
      break

ans = max(width) + max(height)

if notHere == False:
  ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

h, w, m = map(int, input().split())
bomb = []
H = []
W = []
for i in range(m):
    a, b = map(int, input().split())
    H.append(a)
    W.append(b)
    bomb.append([a, b])
countH = Counter(H)
mostH = countH.most_common()
maxH = [mostH[0][0]]
for i in range(len(mostH) - 1):
    if mostH[i][1] == mostH[i + 1][1]:
        maxH.append(mostH[i + 1][0])
    else:
        break
countW = Counter(W)
mostW = countW.most_common()
maxW = [mostW[0][0]]
for i in range(len(mostW) - 1):
    if mostW[i][1] == mostW[i + 1][1]:
        maxW.append(mostW[i + 1][0])
    else:
        break
for i in maxH:
    for j in maxW:
        if [i, j] not in bomb:
            print(countH[i] + countW[j])
            break
    else:
        continue
    break
else:
    print(countH[maxH[0]] + countW[maxW[0]] - 1)

Submission status: Time Limit Exceeded

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

hw_list=[[0 for i in range(w)] for j in range(h)]
h_list=[0]*h
w_list=[0]*w
for i in range(m) :
  a,b=map(int,input().split())
  h_list[a-1]+=1
  w_list[b-1]+=1
  hw_list[a-1][b-1]=1

maxcount=0
for i in range(h) :
  for j in range(w) :
    if hw_list[i][j]==1 :
      count=h_list[i]+w_list[j]-1
      maxcount=max(count,maxcount)
    else :
      count = h_list[i] + w_list[j]
      maxcount = max(count, maxcount)

print(maxcount)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
target = []
for i in range(m):
	target.append(list(map(int, input().split())))

lows = []
columns = []
for l in target:
	lows.append(l[0])
	columns.append(l[1])
u_low = list(set(lows))
u_column = list(set(columns))

ans = 0
for i in u_low:
	for j in u_column:
		count = 0
		for l in target:
			if (l[0] == i) or (l[1] == j):
				count += 1
			ans = max(ans, count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w, m = map(int, input().split())
row = [0 for _ in range(h)]
col = [0 for _ in range(w)]
info = dict()
for _ in range(m):
    x, y = map(int, input().split())
    if x in info:
        info[x].add(y)
    else:
        info[x] = set()
        info[x].add(y)
    row[x-1] += 1
    col[y - 1] += 1

res = 0
for i in range(h):
    tmp = row[i]
    for j in range(w):
        ttmp = (tmp+col[j])
        if i+1 in info and j+1 in info[i+1]:
            ttmp -= 1
        res = max(res, ttmp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

h,w,m= map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
b=[a[i][0] for i in range(m)]
c=[a[i][1] for i in range(m)]
v=Counter(b).most_common()[0][1]
w=Counter(c).most_common()[0][1]
i=[j[0] for j in list(Counter(b).items()) if j[1]==v]
i2=[j[0] for j in list(Counter(c).items()) if j[1]==w]
l=0

for k in i:
    for t in i2:
        
        if([k,t] not in a):
            print(v+w)
            l=1
            break
        
    else:
        continue
    break
if(l==0):
    print(v+w-1)

Submission status: Time Limit Exceeded

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

hw = [list(map(int,input().split())) for x in range(M)]
h = [0]*H #その行に何個対象があるか
w = [0]*W

for p in range(M):
    h[hw[p][0]-1] += 1
    w[hw[p][1]-1] += 1


hmaxichi = [i for i, x in enumerate(h) if x == max(h)]
wmaxichi = [i for i, x in enumerate(w) if x == max(w)]


for q in range(len(hmaxichi)):
    for r in range(len(wmaxichi)):
        if [hmaxichi[q]+1,wmaxichi[r]+1] not in hw:
            flag = 1 #1なら爆破したい場所に爆弾がない場所がある


if flag == 1:
    print(max(h)+max(w))
else:
    print(max(h)+max(w)-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main(H, W, M, obj_h, obj_w, obj):
    c_h = Counter(obj_h)
    c_w = Counter(obj_w)
    max_h = max(c_h.values())
    max_w = max(c_w.values())
    lst_h = [kv[0] for kv in c_h.items() if kv[1] == max_h]
    lst_w = [kv[0] for kv in c_w.items() if kv[1] == max_w]
    for h in lst_h:
        for w in lst_w:
            if [h, w] not in obj:
                print(max_h + max_w)
                exit()
    else:
        print(max_h + max_w - 1)



if __name__ == '__main__':
    H, W, M = list(map(int, input().split()))
    obj = []
    obj_h = []
    obj_w = []
    for _ in range(M):
        i = list(map(int, input().split()))
        obj.append(i)
        obj_h.append(i[0])
        obj_w.append(i[1])
    main(H, W, M, obj_h, obj_w, obj)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
row_list = [0 for _ in range(h)]
col_list = [0 for _ in range(w)]
field = [[0 for _ in range(w)] for _ in range(h)]

for i in range(m):
  hb, wb = map(int, input().split())
  field[hb-1][wb-1] = 1
  row_list[hb-1] += 1
  col_list[wb-1] += 1

r_max_val = max(row_list)
c_max_val = max(col_list)
r_max_idx = [i for i, x in enumerate(row_list) if x == max(row_list)]
c_max_idx = [i for i, x in enumerate(col_list) if x == max(col_list)]

flag = False
for ri in r_max_idx:
  for ci in c_max_idx:
    if not field[ri][ci]:
      flag = True
if flag:
  print(r_max_val + c_max_val)
else:
  print(r_max_val + c_max_val - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect

from sys  import stdin,stdout

from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right

from math import gcd,ceil,floor,sqrt

from collections import Counter,defaultdict,deque,OrderedDict

from queue import Queue,PriorityQueue

from string import ascii_lowercase

sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 998244353
mod = 10**9+7

def isPrime(n):
    
    if (n <= 1) :return False
    if (n <= 3) :return True
    if (n%2 == 0 or n%3 == 0):return False
    for i in range(5,ceil(sqrt(n))+1,6):
        if (n%i==0 or n%(i+2)==0):
            return False
    return True


def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")
    
def DFS(dictionary,vertex,visited):
    visited[vertex]=True
    stack=[vertex]
    print(vertex)
    while stack:
        a=stack.pop()
        for i in dictionary[a]:
            if not visited[i]:
                print(i)
                visited[i]=True
                stack.append(i)


def BFS(dictionary, vertex,visited):
    visited[vertex]=True
    q=deque()
    q.append(vertex)
    while q:
        a=q.popleft()
        for i in dictionary[a]:
            if not visited[i]:
                visited[i]=True
                q.append(i)
                print(i)

                


def soe(limit):
    l=[1]*(limit+1)
    l[0]=0
    l[1]=0
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0
    
    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)
                
def gcd(a,b):
    while b:
        a=a%b
        b,a=a,b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r
    
def solve():
    r,c,m=mp()
    row={}
    col={}
    s=[]
    for i in range(m):
        l=li()
        a=l[0]
        b=l[1]
        row[a]=row.get(a,0)+1
        col[b]=col.get(b,0)+1
    
        s.append(l)
    
    miR,miC=float('-inf'),float('-inf')
    
    for i in row:
        if row[i]>miR:
            miR=row[i]
            R=i
    for i in col:
        if col[i]>miC:
            miC=col[i]
            C=i

    ans=float('-inf')

    for i in col:
        c=miR+col[i]
        if [R,i] in s:
            c-=1
        ans=max(ans,c)

    for  i in row:
        c=miC+row[i]
        if [i,C] in s:
            c-=1
        ans=max(ans,c)

    pr(ans)
        
        
        
            

for _ in range(1):
    solve()

Submission status: Time Limit Exceeded

Solution code:
h, w, n = [int(i) for i in input().split()]
boms = []
for _ in range(n):
    boms.append([(int(i) - 1) for i in input().split()])
baks = []
for i in range(h):
    for j in range(w):
        bak = 0
        for bom in boms:
            if bom[0] == i or bom[1] == j:
                bak += 1
        baks.append(bak)

print(max(baks))

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
if len(h_maxid) * len(w_maxid) > 3 * (10 ** 5): isminus = 0
else:
    for a in h_maxid:
        if isminus == 0: break
        for b in w_maxid:
            if [a, b] in hwList: continue
            isminus = 0
            break
print(max(hList) + max(wList) - isminus)

Submission status: Time Limit Exceeded

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

b=[]

for i in range(m):
  x,y=map(int,input().split())
  b.append([x-1,y-1])

ans=0
for i in range(h):
  for j in range(w):
    bb=b

    c=0
    for abc in bb:
      if abc[0] == i:
        c+=1
        continue
      if abc[1] == j:
        c+=1
    ans=max(ans,c)
print(ans)

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):
        hitList = list(filter(lambda x: x[0] == row + 1, codList))
        counter = len(hitList)
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    for column in range(W):
        hitList = list(filter(lambda x: x[1] == column + 1, codList))
        counter = len(hitList)
        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:
import collections, itertools

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

h_list = list()
w_list = list()

targets = list()

for _ in range(m):
    temp_h, temp_w, = map(int,input().split())

    h_list.append(temp_h)
    w_list.append(temp_w)

    targets.append((temp_h, temp_w))

num_dict_h = dict(collections.Counter(h_list))
num_dict_w = dict(collections.Counter(w_list))

h_candidates = [k for k, v in num_dict_h.items() if v == max(num_dict_h.values())]
w_candidates = [k for k, v in num_dict_w.items() if v == max(num_dict_w.values())]

for temp_h, temp_w in itertools.product(h_candidates, w_candidates):
    if not ((temp_h, temp_w) in targets):
        print(num_dict_h[temp_h] + num_dict_w[temp_w])
        break
else:
    print(num_dict_h[temp_h] + num_dict_w[temp_w] - 1)

Submission status: Time Limit Exceeded

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

bombw = [0]*w
bombh = [0]*h
bomb = [[0 for j in range(w)] for i in range(h)]
# print(bomb)
for i in range(m):
    hi,wi = map(int,input().split())
    bombw[wi-1] += 1
    bombh[hi-1] += 1
    bomb[hi-1][wi-1] = 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 bomb[i][j] == 0:
            print(ans)
            exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
def pointAdd(t,node,tl,tr,index,val):
    if tl == tr:
        t[node] += val
    else:
        mid = (tl+tr)//2
        if index <= mid:
            pointAdd(t,2*node,tl,mid,index,val)
        else:
            pointAdd(t,2*node+1,mid+1,tr,index,val)

        t[node] = max(t[2*node],t[2*node+1])

def main():
    h,w,m = map(int,input().split())
    t = [0]*(4*(w+1))
    rows = {}
    for i in range(m):
        hi,wi = map(int,input().split())
        pointAdd(t,1,0,w-1,wi-1,1)
        if hi not in rows.keys():
            rows[hi] = []

        rows[hi].append(wi)

    ans = 0
    for row in rows.keys():
        curr = len(rows[row])
        for col in rows[row]:
            pointAdd(t,1,0,w-1,col-1,-1)

        curr += t[1]
        ans = max(ans,curr)

        for col in rows[row]:
            pointAdd(t,1,0,w-1,col-1,1)

    print(ans)


main()

Submission status: Time Limit Exceeded

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

freq_w = [ 0 for _ in range(W)]
freq_h = [ 0 for _ in range(H)]
pos = dict()

for _ in range(M):
    h, w = map(int, input().split())
    freq_h[h-1] += 1
    freq_w[w-1] += 1
    pos[(h-1, w-1)] = True


m_w = max(freq_w)
pos_w = [i for i, j in enumerate(freq_w) if j == m_w]

m_h = max(freq_h)
pos_h = [i for i, j in enumerate(freq_h) if j == m_h]

max_ = m_w + m_h - 1
found = False
for i in pos_h:
    for j in pos_w:
        if not((i, j) in pos):
            found = True

print(max_ + int(found))

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
H=[0]*(3*10**5+1)
W=[0]*(3*10**5+1)
M=[]
for i in range(m):
    h,w=map(int,input().split())
    M.append([h,w])
    H[h]+=1
    W[w]+=1

p=max(H)
q=max(W)

X=set([i for i in range(3*10**5+1) if H[i]==p])
Y=set([i for i in range(3*10**5+1) if W[i]==q])

Z=[[M[i][0],M[i][1]] for i in range(m) if M[i][0] in X or M[i][1] in Y ]

cnt=1
flag=True
for x in X:
    if flag:
        for y in Y:
            if not [x,y] in Z:
                cnt=0
                flag=False
                break

print(p+q-cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def resolve():
    H,W,M = map(int,input().split())
    
    Hnum = np.zeros(H+1)
    Wnum = np.zeros(W+1)
    Mdata = [[] for _ in range(H+1) ]
    
    for i in range(M):
        h,w = map(int,input().split())
        Mdata[h].append(w) 
        Hnum[h] += 1
        Wnum[w] += 1
    
    ans = int(max(Hnum) + max(Wnum))
    
    HmaxIdx = np.where(Hnum == Hnum.max())[0]
    WmaxIdx = np.where(Wnum == Wnum.max())[0]
    
    for i in HmaxIdx:
        for j in WmaxIdx:
            if j in Mdata[i]:
                continue
            else:
                return ans
    return ans - 1

ans = resolve()

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 = set()
for i in range(M):
    hi, wi = map(int,input().split())
    tate[hi-1] += 1
    yoko[wi-1] += 1
    bomb.add((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]
'''
tate_max = 0
index_tate = []
for i, v in enumerate(tate):
    if(tate_max < v):
        tate_max = v
        index_tate = [i]
    elif(tate_max == v):
        index_tate.append(i)
#print(tate_max, index_tate)

yoko_max = 0
index_yoko = []
for i, v in enumerate(yoko):
    if(yoko_max < v):
        yoko_max = v
        index_yoko = [i]
    elif(yoko_max == v):
        index_yoko.append(i)
#print(yoko_max, index_yoko)


#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)
'''

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,m = map(int,input().split())
L = [[0]*w for i in range(h)]

for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    L[a][b] = 1
L = np.array(L)
T = np.rot90(L,k =-1)
#print(L)
#print(T)
L_num = []
T_num = []
for i in range(h):
    L_num.append(sum(L[i]))
for i in range(w):
    T_num.append(sum(T[i]))
    
ans = 0
sum1 = 0
for i in range(h):
    
    for j in range(w):
        
        sum1 +=L_num[i] + T_num[j]
        #print(L[i],T[j],sum1)
        if L[i][j] ==1:
            sum1 -=1
        ans = max(ans,sum1)
        sum1 = 0
print(ans)

Submission status: Time Limit Exceeded

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

H_bomb = [0]*H
W_bomb = [0]*W
S = set()

for _ in range(m):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    S.add(tuple([h, w]))
    H_bomb[h] += 1
    W_bomb[w] += 1

H_max = max(H_bomb)
W_max = max(W_bomb)

H_memo = []
W_memo = []

for i in range(H):
    if H_bomb[i] == H_max:
        H_memo.append(i)

for j in range(W):
    if W_bomb[j] == W_max:
        W_memo.append(j)

ans = H_max + W_max

daburi = 1

for i in H_memo:
    for j in W_memo:
        if tuple([i, j]) not in S:
            daburi = 0
print(ans - daburi)

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
#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 = 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)]
# M = [[] for _ in range(m)]
for i in range(m):
    mh, mw = list(map(int, input().split()))
    X[mh-1][mw-1] = 1
    # M[i] = [mh, mw]
    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

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if X[i][j] == 0:
                ans += 1
                flag = True
                break
        if flag:
            break

# print(M)
# print(X)
# print(count_row, count_col)
# print(max_row_index, max_col_index)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
tgts=set()
for _ in range(M):
    i,j=map(int,input().split())
    tgts.add((i,j))

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

for i,j in tgts:
    rows[i]+=1
    cols[j]+=1

ii=max(rows)
jj=max(cols)

ia=[i for i in range(H+1) if rows[i]==ii]
ja=[j for j in range(W+1) if cols[j]==jj]

ans=0
for i in ia:
    for j in ja:
        k=rows[i]+cols[j]
        if (i,j) in tgts:
            k-=1
        ans=max(ans,k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

H,W,M = map(int,input().split())
bomb = [[0,0] for _ in range(M)]
bomb_d = defaultdict(int)

for i in range(M):
    bomb[i] = list(map(int,input().split()))
    bomb[i][0] -= 1
    bomb[i][1] -= 1
    bomb_d[tuple(bomb[i])] = 1


dh = [0]*H
dw = [0]*W

for i in range(M):
    dh[bomb[i][0]] += 1
    dw[bomb[i][1]] += 1

Maxh = max(dh)
Maxw = max(dw)

h_p = []
w_p = []

for i in range(H):
    if dh[i] == Maxh:
        h_p.append(i)
for i in range(W):
    if dw[i] == Maxw:
        w_p.append(i)

f = 0
for h in h_p:
    for w in w_p:
        if bomb_d[(h,w)] != 1:
            f = 1

if f == 0:
    print(Maxh+Maxw-1)
else:
    print(Maxh+Maxw)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    H, W, M = mis()
    B = set()
    BH = [0]*H
    BW = [0]*W
    for _ in range(M):
        h, w = mis()
        h -= 1
        w -= 1
        BH[h] += 1
        BW[w] += 1
        B.add((h, w))
    #
    maxbh = max(BH)
    maxbw = max(BW)
    for h in filter(lambda hh: BH[hh]==maxbh, range(H)):
        for w in filter(lambda ww: BW[ww]==maxbw, range(W)):
            if (h, w) not in B:
                print(maxbh + maxbw)
                return
    print(maxbh + maxbw - 1)







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,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[[0 for i in range(w)] for i in range(h)]
for i in range(n):
    a,b=map(int,input().split())
    L[a-1][b-1]=1
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
H_max=[i+1 for i, x in enumerate(H) if x == h_max]
W_max=[i+1 for i, x in enumerate(W) if x == w_max]
ans=h_max+w_max-1
for hh in H_max:
    for ww in W_max:
        if L[hh-1][ww-1]==0:
            ans+=1
            break
    else:
        continue
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np

if __name__ == '__main__':
    H, W, M = list(map(lambda x: int(x), sys.stdin.readline().split()))

    dic = {}
    # h = [0 for i in range(H)]
    # w = [0 for i in range(W)]
    h = np.zeros(H, dtype=np.int64)
    w = np.zeros(W, dtype=np.int64)
    for i in range(M):
        # P.append(list(map(lambda x: int(x), sys.stdin.readline().split())))
        x, y = list(map(lambda x: int(x), sys.stdin.readline().split()))
        x -= 1
        y -= 1
        h[x] += 1
        w[y] += 1
        dic[x*H+y] = 1
    
    lh = np.where(h == h.max())
    lw = np.where(w == w.max())

    mx = np.max(h)
    my = np.max(w)
    # print(mx, my)

    # print(lh[0])
    # print(lw[0])
    max = 0
    for i in lh[0]:
        for j in lw[0]:
            tmp = h[i] + w[j]
            if i*H+j in dic:
                tmp -= 1
            if tmp > max:
                max = tmp
    print(max)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = [int(m) for m in input().split(" ")]
bombByCol = [0] * W
bombByRow = [0] * H
A = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
  tmp = [int(a) for a in input().split(" ")]
  h = tmp[0] - 1
  w = tmp[1] - 1
  bombByCol[w] += 1
  bombByRow[h] += 1
  A[h][w] += 1

maxC = 0
idxC = []
maxR = 0
idxR = []
for j in range(len(bombByCol)):
  if maxC > bombByCol[j]:
    continue
  elif maxC == bombByCol[j]:
    idxC.append(j)
  elif maxC < bombByCol[j]:
    maxC = bombByCol[j]
    idxC = [j]
for k in range(len(bombByRow)):
  if maxR > bombByRow[k]:
    continue
  elif maxR == bombByRow[k]:
    idxR.append(k)
  elif maxR < bombByRow[k]:
    maxR = bombByRow[k]
    idxR = [k]

bombFlag = 1
for j in idxC:
  for k in idxR:
    if A[k][j] == 0:
      bombFlag = 0
      break
  if bombFlag == 0:
    break

print(maxC + maxR - bombFlag)