Problem:


Score : 500 points

Problem Statement

We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i-th target is \left(h_i, w_i \right).

Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.

Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.

Constraints

All values in input are integers.

1 \leq H, W \leq 3 \times 10^5

1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)

1 \leq h_i \leq H

1 \leq w_i \leq W

\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

We can destroy all the targets by placing the bomb at \left(1, 2\right).

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4

Sample Output 3

6



Sample input:
2 3 3
2 2
1 1
1 3


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append([h, w])
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
k = 0
while k < H:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while k < W:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:  
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      if [h, w] not in bomb:
        ans += 1
        break
    else:
      continue
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = deque([])
k = 0
while k < H:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while k < W:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:  
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      if grid[h][w] == 0:
        ans += 1
        break
    else:
      continue
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = np.zeros(h, dtype=int)
    col = np.zeros(w, dtype=int)
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    r = row.max()
    c = col.max()
    for ri in np.arange(h)[row == r]:
        for ci in np.arange(w)[col == c]:
            if (ri, ci) not in target:
                print(r + c)
                return
    print(r + c - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = deque([])
k = 0
while len(counth) > 0:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while len(countw) > 0:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
if len(index_h)*len(index_w) > M:
  ans += 1
else:  
  while len(index_h) > 0:
    h = index_h.pop()
    while len(index_w) > 0:
      w = index_w.pop()
      if grid[h][w] == 0:
        ans += 1
        break
    else:
      continue
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = deque([])
k = 0
while len(counth) > 0:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while len(countw) > 0:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
while len(index_h) > 0:
  h = index_h.pop()
  while len(index_w) > 0:
    w = index_w.pop()
    if grid[h][w] == 0:
      ans += 1
      break
  else:
    continue
  break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
stage = [[0 for w in range(W)] for h in range(H)]
for m in range(M):
    h,w = map(int,input().split())
    stage[h-1][w-1] = 1
ans = 0
for h in range(H):
    for w in range(W):
        tmp = 0
        tmp += sum([stage[h][ww] for ww in range(W)])
        tmp += sum([stage[hh][w] for hh in range(H)])
        if stage[h][w] == 1:
            tmp -= 1
        ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

bomb = []
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb.append([h, w])
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

ans = 0
flg = False
for r in r_check:
    if flg:
        break
    for c in c_check:
        if [r, c] in bomb:
            ans = row[r] + column[c] - 1
        else:
            ans = row[r] + column[c]
            flg = True
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0]*h
res2=[0]*w
for i in range(m):
    bomb1=bomb[i]
    res1[bomb1[0]-1]+=1
    res2[bomb1[1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=[]
for j in range(h):
    res3=res1[j]
    if res3>s1:
            l1=[j+1]
            s1=res3
    elif res3==s1:
            l1.append(j+1)
s2=0
l2=[]
for k in range(w):
    res4=res2[k]
    if res4>s2:
            l2=[k+1]
            s2=res4
    elif res4==s2:
            l2.append(k+1)
count=0
for l in range(m):
    bomb2=bomb[l]
    if bomb2[0] in l1 and bomb2[1] in l2:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
print(s)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = []
index_w = []
for k in range(H):
  if counth[k] == maxh:
    index_h.append(k)
for k in range(W):
  if countw[k] == maxw:
    index_w.append(k)
ans = maxh + maxw - 1
for h in index_h:
  for w in index_w:
    if grid[h][w] == 0:
      ans += 1
      break
  else:
    continue
  break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0 for _ in range(h)]
res2=[0 for _ in range(w)]
for i in range(m):
    res1[bomb[i][0]-1]+=1
    res2[bomb[i][1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=[]
for j in range(h):
    if res1[j]>s1:
            l1=[j+1]
            s1=res1[j]
    elif res1[j]==s1:
            l1.append(j+1)
s2=0
l2=[]
for k in range(w):
    if res2[k]>s2:
            l2=[k+1]
            s2=res2[k]
    elif res2[k]==s2:
            l2.append(k+1)
count=0
for l in range(m):
    bomb1=bomb[l]
    if bomb1[0] in l1 and bomb1[1] in l2:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

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

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

exist = [[False]*W for _ in range(H)]
for i in range(M):
    exist[h[i]][w[i]]=True

from collections import Counter
ch = Counter(h)
cw = Counter(w)
#print( max(ch[x]+cw[y]-exist[x][y] for x in range(H) for y in range(W) ))

x_max=max(ch.values())
cand_x_max1 = [x for x in range(H) if ch[x]==x_max]
cand_x_max2 = [x for x in range(H) if ch[x]==x_max-1]

y_max=max(cw.values())
cand_y_max1 = [y for y in range(W) if cw[y]==y_max]
cand_y_max2 = [y for y in range(W) if cw[y]==y_max-1]

from itertools import product
found=False
for x, y in product(cand_x_max1,cand_y_max1):
    if not exist[x][y]:
        found=True
        break
if found:
    print(x_max+y_max)
else:
    print(x_max+y_max-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h, w = [], []
h_dic, w_dic = {}, {}

for i in range(M):
    h_i, w_i = map(int, input().split())
    h.append(h_i)
    w.append(w_i)
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])

max_count = 0
for mh in max_h_items:
    for mw in max_w_items:
        count = 0
        for i in range(M):
            if h[i] == mh[0] or w[i] == mw[0]:
                count += 1
        max_count = max(max_count, count)
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        b=B[ch]
        for cw in CW:
            if cw in b:
                continue
            else:
                flag=1
                break
        if flag:
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        for cw in CW:
            if cw in B[ch]:
                continue
            else:
                flag=1
                break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
flag=0
for ch in CH:
    for cw in CW:
        if cw in B[ch]:
            continue
        else:
            flag=1
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

Submission status: Time Limit Exceeded

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

h, w, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
CC = [[] for i in range(h)]
for i in range(m):
    CC[C[i][0]-1].append(C[i][1]-1)

for i in range(h):
    CC[i].sort()

A = [0] * h
B = [0] * w
for i in range(m):
    A[C[i][0]-1] += 1
    B[C[i][1]-1] += 1

# ans = 0
# for i in range(m):
#     ans = max(ans, A[C[i][0]-1] + B[C[i][1]-1] - 1)

D = [[A[i], i] for i in range(h)]
E = [[B[i], i] for i in range(w)]
D.sort(reverse=True)
E.sort(reverse=True)

# print(D,E)

from bisect import bisect
# if not ([D[0][1]+1, E[0][1]+1] in C):
#     # print("r1")
#     ans = D[0][0] + E[0][0]
# else:
ans = 0
aa = D[0][0] + E[0][0]
co = 0
F = []

for i in range(h):
    for j in range(w):
        if D[i][0] + E[j][0] == aa:
            F.append([D[i][1], E[j][1]])
            co += 1
        else:
            break
    # if co > m:
    #     break
# if co > m:
#     # print("r2")
#     ans = D[0][0] + E[0][0]
else:
    ha = 0
    # print(F)
    # print(CC)
    for i in range(len(F)):
        ind = bisect(CC[F[i][0]], F[i][1])
        if ind==0 or (ind >= 1 and CC[F[i][0]][ind-1] != F[i][1]):
            # print(CC[ind-1], F[i][1])
            ha = 1
            break
    if ha == 1:
        # print("r3")
        ans = D[0][0] + E[0][0]
    else:
        # print("m1")
        ans = D[0][0] + E[0][0] - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
h = {}
w = {}
bombs = []
for i in range(M):
    x, y = list(map(int, input().split()))
    if x in h:
        h[x] += 1
    else:
        h[x] = 1
    if y in w:
        w[y] += 1
    else:
        w[y] = 1
    bombs.append([x, y])

hmax = [k for k, v in h.items() if v == max(h.values())]
wmax = [k for k, v in w.items() if v == max(w.values())]

ans = 0
max = 0

for x in hmax:
    for y in wmax:
        ans = h[x] + w[y]
        if ans > max:
            max = ans - 1 if [x, y] in bombs else ans

print(max)

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=dict()
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)

N=len(mh)*len(mw)

for i in range(M):
    x,y=A[i]
    if x in mh and y in mw:
        N-=1

if N ==0: ans-=1

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
mine=[list(map(int,input().split()))for i in range(M)]
mine_h=[0]*H
mine_w=[0]*W
ans=0
val=-1
for i in range(M):
    mine_h[mine[i][0]-1]+=1
    mine_w[mine[i][1]-1]+=1
max_h=max(mine_h)
max_w=max(mine_w)
h_index=[i+1 for i, x in enumerate(mine_h)if x == max_h]
w_index=[i+1 for i, x in enumerate(mine_w)if x == max_w]
for i in h_index:
    for j in w_index:
        if [i,j] in mine:
            continue
        else:
            val=0
            break
print(max_h+max_w+val)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
HW.sort()
# print(*HW,sep='\n')
# print('---')

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]


for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# # print('---')
# # print(sum_h)
# # print(sum_w)
# # print('---')
sum_h.sort(reverse=True)
sum_w.sort(reverse=True)
# print(sum_h)
# print(sum_w)

max_bombs = 0
if sum_h[0][0] > sum_w[0][0]:
    for w_bombs, w_index in sum_w:
        bombs = sum_h[0][0] + w_bombs
        if [sum_h[0][1], w_index] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

else:
    for h_bombs, h_index in sum_h:
        bombs = sum_w[0][0] + h_bombs
        if [h_index, sum_w[0][1]] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

# for h_bombs, h_index in sum_h:
#     for w_bombs, w_index in sum_w:
#         bombs = h_bombs + w_bombs
#         if [h_index, w_index] in HW:
#             bombs -= 1
#         if max_bombs < bombs:
#             max_bombs = bombs
print(max_bombs)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
# print(HW)

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]

for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# print('---')
# print(sum_h)
# print(sum_w)
# print('---')
sum_h.sort(reverse=True)
sum_w.sort(reverse=True)
# print(sum_h)
# print(sum_w)

max_bombs = 0
for h_bombs, h_index in sum_h:
    # print(h_bombs, h_index)
    for w_bombs, w_index in sum_w:
        bombs = h_bombs + w_bombs
        if [h_index, w_index] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

print(max_bombs)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
h = {}
w = {}
for i in range(M):
    x, y = list(map(int, input().split()))
    if x in h:
        h[x].append(y)
    else:
        h[x] = [y]
    if y in w:
        w[y].append(x)
    else:
        w[y] = [x]

ans = 0
max = 0

for x in h:
    for y in w:
        ans = len(h[x]) + len(w[y])
        if ans > max:
            max = ans - 1 if y in h[x] else ans
            
print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.readline
h, w, m = map(int, input().split())
dh = dict()
dv = dict()
t = set()
for _ in range(m):
	a, b = map(int, input().split())
	a, b = a-1, b-1
	t.add((a, b))
	if a in dh: dh[a] += 1
	else: dh[a] = 1
	if b in dv: dv[b] += 1
	else: dv[b] = 1

store1, store2 = [], []
m1, m2 = 0, 0
for v in dh.values(): m1 = max(m1, v)
for k, v in dh.items():
	if v == m1: store1.append((k, v))

for v in dv.values(): m2 = max(m2, v)
for k, v in dv.items():
	if v == m2: store2.append((k, v))

ans = 0
for i in store1:
	for j in store2:
		i1, l1 = i
		i2, l2 = j
		m = -1 if (i1, i2) in t else 0
		ans = max(ans, l1 + l2 + m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
bomb=[]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  bomb.append((h,w))
 
qh=[]
qw=[]
maxh=max(sumh)
maxw=max(sumw)
qh=[i for i,x in enumerate(sumh) if x==maxh]
qw=[i for i,x in enumerate(sumw) if x==maxw]

cnt=0
for h,w in bomb:
  if (h-1) in qh and (w-1) in qw:
    cnt+=1
if cnt==len(qh)*len(qw):
  print(maxh+maxw-1)
else:
  print(maxh+maxw)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = list(map(int, input().split()))
h = {}
w = {}
for i in range(M):
    x, y = list(map(int, input().split()))
    if x in h:
        h[x].append(y)
    else:
        h[x] = [y]
    if y in w:
        w[y].append(x)
    else:
        w[y] = [x]

ans = 0
max = 0

for x in h:
    for y in w:
        ans = len(h[x]) + len(w[y])
        if y in h[x]:
            ans -= 1
        if ans > max:
            max = ans

print(max)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hw = [list(map(int, input().split())) for i in range(m)]
ht = [0] * h
wt = [0] * w
for i in range(m):
    ht[hw[i][0]-1] += 1
    wt[hw[i][1]-1] += 1
maxhw = [max(ht), max(wt)]
for i in [i for i, x in enumerate(ht) if x == maxhw[0]]:
    for j in [j for j, y in enumerate(wt) if y == maxhw[1]]:
        if [i+1, j+1] not in hw:
            print(sum(maxhw))
            break
    else:
        continue
    break
else:
    print(sum(maxhw)-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline
 
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))
mh = max(Hsum)
mw = max(Wsum)
hmax_ind = list(map(lambda x: True if x == mh else False, Hsum))
hmax_ind = list(itertools.compress(range(len(Hsum)), hmax_ind))
wmax_ind = list(map(lambda x: True if x == mw else False, Wsum))
wmax_ind = list(itertools.compress(range(len(Wsum)), wmax_ind))
 
res = []
for n1, n2 in itertools.product(hmax_ind, wmax_ind):
  res.append(str(n1)+"_"+str(n2))
 
if len(set(res).intersection(set(hw))) == len(res):
  print(mh + mw-1)
else:
  print(mh + mw)

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] = '#'

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from sys import exit

def maxindexes(L,Lmax):
    ret = []
    for i in range(len(L)):
        if L[i] == Lmax:
            ret.append(i)
    
    return ret


H,W,M = map(int,input().split())
row = [0]*H
col = [0]*W
bomb = []

for _ in range(M):
    a,b = (int(x)-1 for x in input().split())
    row[a] += 1
    col[b] += 1
    bomb.append((a,b))

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

rmaxind= maxindexes(row,rmax)
cmaxind = maxindexes(col,cmax)

for p in product(rmaxind,cmaxind):
    if p not in bomb:
        print(rmax+cmax)
        exit(0)

print(rmax+cmax-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = set()
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw.add((h-1, w-1))

hcnt = Hsum.count(max(Hsum))
wcnt = Wsum.count(max(Wsum))
if hcnt * wcnt > M:
  print(max(Hsum) + max(Wsum))
  sys.exit()

hidx = [i for i, _ in enumerate(Hsum) if _ == max(Hsum)]
widx = [i for i, _ in enumerate(Wsum) if _ == max(Wsum)]
for h in hidx:
  for w in widx:
    if (h, w) not in hw:
      print(max(Hsum) + max(Wsum))
      sys.exit()
print(max(Hsum) + max(Wsum) - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
s=[[] for _ in range(H)]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  s[h-1].append(w-1)
 
qh=[]
qw=[]
maxh=max(sumh)
maxw=max(sumw)
for i in range(H):
  if maxh==sumh[i]:
    qh.append(i)
for i in range(W):
  if maxw==sumw[i]:
    qw.append(i)
 
#print(s,H,W,sumh,sumw,qh,qw)
for i in qh:
  for j in qw:
    if j not in s[i]:
      print(maxh+maxw)
      exit()
 
print(maxh+maxw-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
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 += [(h-1, w-1)]

hcnt = Hsum.count(max(Hsum))
wcnt = Wsum.count(max(Wsum))
if hcnt * wcnt > M:
  print(max(Hsum) + max(Wsum))
  sys.exit()

hidx = [i for i, _ in enumerate(Hsum) if _ == max(Hsum)]
widx = [i for i, _ in enumerate(Wsum) if _ == max(Wsum)]
for h in hidx:
  for w in widx:
    if (h, w) not in hw:
      print(max(Hsum) + max(Wsum))
      sys.exit()

print(max(Hsum) + max(Wsum) - 1)

Submission status: Time Limit Exceeded

Solution code:
import  collections

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

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.add((h, w))

H_count_sort = sorted(H_count.items(), key=lambda x: x[1])
W_count_sort = sorted(W_count.items(), key=lambda x: x[1])

max_count = 0
for h_count in reversed(H_count_sort):
    for w_count in reversed(W_count_sort):
        count = h_count[1] + w_count[1]
        if (h_count[0], w_count[0]) in points:
            count -= 1

        if max_count > count:
            break
        max_count = max(max_count, count)

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import  collections

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

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.add((h, w))

max_count = 0

for h, h_count in H_count.items():
    for w, w_count in W_count.items():
        count = h_count + w_count
        if (h, w) in points:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import  collections

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

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = []
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.append((h, w))

max_count = 0

for h, h_count in H_count.items():
    for w, w_count in W_count.items():
        count = h_count + w_count
        if (h, w) in points:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hw = []

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


    hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]
    hmaxset = set(hmax)
    wmaxset = set(wmax)

    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1
    if count != len(hmax) * len(wmax):
        flag = True

    if flag:
        print(Hlist[hmax[0]] + Wlist[wmax[0]])
    else:
        print(Hlist[hmax[0]] + Wlist[wmax[0]] - 1)





if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,input().split(" "))
ar = []
br = [0 for i in range(h)]
cr = [0 for i in range(w)]
for i in range(n):
    r = list(map(int,input().split(" ")))
    ar.append(r)
    br[r[0]-1] += 1
    cr[r[1]-1] += 1
mx = 0
count = 0
for i in range(h):
    for j in range(w):
        if [i+1,j+1] in ar:
            count -= 1
        count += br[i] + cr[j]
        if count > mx:
            mx = count
        count = 0
print(mx)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w, m = map(int, input().split())
    bombs_h = [0] * h
    bombs_w = [0] * w
    B = []
    for n in range(m):
        h1, w1 = map(int, input().split())
        B.append((h1-1, w1-1))
        bombs_w[w1-1] += 1
        bombs_h[h1-1] += 1
    h_maxindex = [i for i, x in enumerate(bombs_h) if x == max(bombs_h)]
    w_maxindex = [i for i, x in enumerate(bombs_w) if x == max(bombs_w)]
    max_h = max(bombs_h)
    max_w = max(bombs_w)
    cnt = 0
    k = len(h_maxindex) * len(w_maxindex)
    for i, j in B:
        if bombs_h[i] == max_h and bombs_w[j] == max_w:
            cnt += 1
    ans = max_h + max_w - (cnt == k)
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

h_bom = [0] * H
w_bom = [0] * W

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

    h_bom[h[i] - 1] += 1
    w_bom[w[i] - 1] += 1

h_max = max(h_bom)
w_max = max(w_bom)

h_list = []
w_list = []

for i in range(len(h_bom)):
    if h_bom[i] == h_max:
        h_list.append(i)

for i in range(len(w_bom)):
    if w_bom[i] == w_max:
        w_list.append(i)

for y in h_list:
    for x in w_list:
        flag = True
        for i in range(M):
            if y == (h[i] - 1) and x == (w[i] - 1):
                flag = False

        if flag:
            print(h_max + w_max)
            sys.exit()

print(h_max + w_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,n = map(int,input().split(" "))
ar = []
for i in range(n):
    br = list(map(int,input().split(" ")))
    ar.append(br)
mx = 0
a,b = 0,0
for i in range(1,h+1):
    for j in range(1,w+1):
        count = 0
        for r in ar:
            if r[0] == i or r[1] == j:
                count += 1
        if count > mx:
            mx = count
print(mx)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
H,W,M=map(int,input().split())
Bomb_ls=set()
R=[0]*H
C=[0]*W
for i in range(M):
  X,Y=[int(x) for x in input().split()]
  Bomb_ls.add((X-1,Y-1))
  R[X-1]+=1
  C[Y-1]+=1
R_max=[i for i, x in enumerate(R) if x == max(R)]
C_max=[i for i, x in enumerate(C) if x == max(C)]
if len(R_max)*len(C_max)>M:
  print(max(R)+max(C))
else:
  score=-1
  for r in R_max:
    for c in C_max:
      if not (r,c) in Bomb_ls:
        score=0
        break
  print(max(R)+max(C)+score)