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())
row_list = [0 for _ in range(h)]
col_list = [0 for _ in range(w)]
log = []

for i in range(m):
  hb, wb = map(int, input().split())
  log.append([hb-1, wb-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:
    tmp_flag = True
    for i in range(m):
      hb, wb = log[i]
      if ci == wb and ri == hb:
        tmp_flag = False
    if tmp_flag:
      flag = True
      break
  if flag:
    break
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:
h,w,m = map(int,input().split())
gyou = [0]*h
retu = [0]*w
zahyo = []
kiroku = []
for i in range(m):
    zahyo = list(map(int,input().split()))
    kiroku.append(zahyo)
    gyou[zahyo[0]-1] += 1
    retu[zahyo[1]-1] += 1
    
maxg = max(gyou)
maxlistg = [i for i,v in enumerate(gyou) if v == maxg]
maxr = max(retu)
maxlistr = [i for i,v in enumerate(retu) if v == maxr]

answer = 0
counter = maxg + maxr
for i in maxlistg:
    if answer == 1:
        break
    for j in maxlistr:
        if [i+1,j+1] not in kiroku:
            answer = 1
            break
if answer == 0:
    print(counter-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

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

list1 = []
listh = [0 for i in range(H+1)]
for i in range(M):
    list1.append(list(map(int, input().split())))
    listh[list1[i][0]]+=1


max1 = max(listh)
loc1 = [0]

for i in range(1, len(listh)):
    if max1 == listh[i]:
        loc1.append(i)

#print("Loc1 is ", loc1)
max2_total = 0
for jjj in range(1, len(loc1)):
    listw = [0 for i in range(W+1)]
    #print("jjj is ",jjj)
    for k in range(M):
        if list1[k][0] == loc1[jjj]:
            continue
        listw[list1[k][1]]+=1
    #print("listw is",listw)
    max2 = max(listw)
    #print("max2 is ",max2)
    if max2_total<max2:
        max2_total = max2
    if max2 == H:
        break

print(max1 + max2_total)

Submission status: Time Limit Exceeded

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

L = [ 0 for i in range(M)]
for i in range(M):
  L[i] = tuple( map(int, input().split()) )

H_val = [ 0 for i in range(H+1)]
W_val = [ 0 for i in range(W+1)]
for i in L:
  H_val[ i[0] ] += 1
  W_val[ i[1] ] += 1
  
Hm = 0
Hs = set()
Wm = 0
Ws = set()
for i in range(1, H+1):
  if H_val[i] == Hm:
    Hs.add(i)
  elif H_val[i] > Hm:
    Hs = {i}
    Hm = H_val[i]
for i in range(1, W+1):
  if W_val[i] == Wm:
    Ws.add(i)
  elif W_val[i] > Wm:
    Ws = {i}
    Wm = W_val[i]
  
flg = False
for i in Hs:
  for j in Ws:
    if (i,j) not in L:
      flg = True
      break
  if flg:
    break
if flg:
  print( Hm + Wm )
else:
  print( Hm + Wm - 1)

Submission status: Time Limit Exceeded

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

h_obj=[0]*(h+1)
w_obj=[0]*(w+1)
hw_grid=[]
for _ in range(m):
  li=list(map(int,input().split()))
  hw_grid.append(li)
  h_obj[li[0]]+=1
  w_obj[li[1]]+=1
  
def index_Multi(List,liter):
    #Listはリスト本体・literは検索したい文字
    index_L = []
    for val in range(0,len(List)):
        if liter == List[val]:
            index_L.append(val)
    return index_L
  
max_h=max(h_obj)
max_w=max(w_obj)

max_h_li=index_Multi(h_obj,max_h)
max_w_li=index_Multi(w_obj,max_w)

#print("max_w_li",max_w_li)
#print("max_h_li",max_h_li)
#print(hw_grid)

set_list=[]
for H in max_h_li:
  for W in max_w_li:
    set_list.append([H,W])

set_list=[str(pair) for pair in set_list]
hw_grid=[str(pair) for pair in hw_grid]

#print("set_list",set_list)
#print("hw_grid",hw_grid)

#print("set(set_list)-set(hw_grid)",list(set(set_list)-set(hw_grid)))

if len(list(set(set_list)-set(hw_grid))) !=0:
  print(max(h_obj)+max(w_obj))
else:
  print(max(h_obj)+max(w_obj)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    h, w, m = LI()
    mat = [[0 for i in range(w+1)] for i in range(h+1)]
    hs = defaultdict(int)
    ws = defaultdict(int)
    for i in range(m):
        hi, wi = LI()
        mat[hi][wi] = 1
        hs[hi] += 1
        ws[wi] += 1

    hsums_top = set()
    wsums_top = set()

    maxh = 0
    for i, top in hs.items():
        if maxh == top:
            hsums_top.add(i)
        elif maxh < top:
            maxh = top
            hsums_top = {i}

    maxw = 0
    for i, top in ws.items():
        if maxw == top:
            wsums_top.add(i)
        elif maxw < top:
            maxw = top
            wsums_top = {i}

    if len(hsums_top) * len(wsums_top) > m:
        print(maxh + maxw)
        return
    for i in hsums_top:
        for j in wsums_top:
            if mat[i][j] == 0:
                print(maxh + maxw)
                return
    print(maxh + maxw - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
Hs = []
Ws = []
Hs_count = []
Ws_count = []
zahyo = []
for i in range(M):
    h,w = map(int,input().split())
    zahyo.append(f"{h} {w}")
    Hs.append(h)
    Ws.append(w)
for i in range(1,H+1):
    Hs_count.append(Hs.count(i))
for i in range(1,W+1):
    Ws_count.append(Ws.count(i))
maxIndex_H = [i for i, x in enumerate(Hs_count) if x == max(Hs_count)]
maxIndex_W = [i for i, x in enumerate(Ws_count) if x == max(Ws_count)]

n = len(maxIndex_H)*len(maxIndex_W)
for i in maxIndex_H:
    for j in maxIndex_W:
        if zahyo.count(f"{i+1} {j+1}") == 1:
            n -= 1

if n <= 0:
    print(max(Hs_count)+max(Ws_count)-1)
else:
    print(max(Hs_count)+max(Ws_count))

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxCount]
if maxCount==0:
  print(0)
  sys.exit()


maxCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxCount]

#counterList = []
#for maxH in maxHList:
#  for maxW in maxWList:
#    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
#print(max(counterList))
print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

h = np.array([0]*H)
w = np.array([0]*W)

bom= np.array([[0]*W]*H)

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

ans = []

for i in range(H):
   ans.append(max(w + h[i] - bom[i])) 

print(max(ans))

Submission status: Time Limit Exceeded

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

hl=[0]*h
wl=[0]*w

for hm,wm in l:
  hl[hm-1]+=1
  wl[wm-1]+=1

hmax=max(hl)
wmax=max(wl)

hmax_idx=[i for i,v in enumerate(hl) if v==hmax]
wmax_idx=[i for i,v in enumerate(wl) if v==wmax]

add=-1
for j in hmax_idx:
  for i in wmax_idx:
    if not [j+1,i+1] in l:
      add=0

print(hmax+wmax+add)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from time import clock
a=clock()
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(s, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if s[mid] == val:return mid
        elif s[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,s):
    for i in range(1,n):s[i]+=s[i-1]
    return s;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# code start from here-

r,w,m=iia()
row,col,arr={},{},{}
for i in range(m):
    a,b=iia()
    if a in row:
        row[a]+=1
    else:
        row[a]=1
    if b in col:
        col[b]+=1
    else:
        col[b]=1
    arr[(a,b)]=1
ans=0
for k1,val1 in row.items():
    for k2,val2 in col.items():
        if (k1,k2) in arr:
            ans=max(ans,val1+val2-1)
        else:
            ans=max(ans,val1+val2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


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


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


def main():
    h, w, m = MI()
    targets = [[] for i in range(h)]
    tate = [[] for i in range(w)]
    original = []
    lengths = [0] * h
    for i in range(m):
        target = LI()
        original.append(target)
        targets[target[0] - 1].append(target[1] - 1)
        tate[target[1] - 1].append(target[0] - 1)
        lengths[target[0] - 1] += 1

    max_length = max(lengths)
    max_h_indexes = [i for i, x in enumerate(lengths) if x == max_length]
    semi_max_h_indexes = [i for i, x in enumerate(
        lengths) if x == max_length - 1]

    for j in range(len(tate)):
        tate[j] = set(tate[j])
    ans = 0

    for index in max_h_indexes:
        for j in range(w):
            if index in tate[j]:
                ans = max(ans, len(tate[j]) + lengths[index] - 1)
            else:
                ans = max(ans, len(tate[j]) + lengths[index])
    for index in semi_max_h_indexes:
        for j in range(w):
            if index in tate[j]:
                ans = max(ans, len(tate[j]) + lengths[index] - 1)
            else:
                ans = max(ans, len(tate[j]) + lengths[index])

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
column = [0 for i in range(h+1)]
row = [0 for i in range(w+1)]
column_max = 0
row_max = 0
column_max_index = []
row_max_index = []
matrix = [[0 for i in range(w+1)] for i in range(h+1)]

for i in range(m):
  a,b = map(int, input().split())
  column[a] += 1
  row[b] += 1
  if column[a] == column_max:
    column_max_index.append(a)
    
  if column[a] > column_max:
    column_max = column[a]
    column_max_index = [a]
  
  if row[b] == row_max:
    row_max_index.append(b)
    
  if row[b] > row_max:
    row_max = row[b]
    row_max_index = [b]
  matrix[a][b] = 1
  
count = 0
for i in column_max_index:
  for j in row_max_index:
    if matrix[i][j] == 0:
      count += 1
      break
if count != 0:
  print(column_max + row_max)
else:
  print(column_max + row_max - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
smat=[list(map(int,input().split())) for i in range(m)]
hb=[d[0] for d in smat]
wb=[d[1] for d in smat]
cmax=0
for i in range(h):
    for j in range(w):
        c=hb.count(i+1)+wb.count(j+1)
        if [i+1,j+1] in smat:
            c=c-1
        if cmax<c:
            cmax=c
print(cmax)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, m = map(int, input().split())
bomb_list = []
for _ in range(m):
    bomb = list(map(int, input().split()))
    bomb_list.append(bomb)

grid = [0]*w
arr = np.array(grid)
for _ in range(h-1):
    if h == 1:
        break
    else:
        add = np.array(grid)
        arr = np.concatenate([arr, add])

arr = arr.reshape([h,w])
for list in bomb_list:
    h_point = list[0]-1
    w_point = list[1]-1
    arr[h_point][w_point] = 1

maximum = 0
for i in range(h):
    for j in range(w):
        cnt = 0
        cnt += np.count_nonzero(arr[i])
        cnt += np.count_nonzero(arr[:,j])
        if arr[i,j] == 1:
            cnt -= 1
        if maximum < cnt:
            maximum = cnt

print(maximum)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

ans = 0
for i in mode_h:
    for j in mode_w:
        if ans == H + W - 1:
            print(ans)
            exit()
        if ans < h.count(i) + w.count(j):
            ans = h.count(i) + w.count(j)
            for k in range(M):
                if h[k] == i and w[k] == j:
                    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
H,W,M=map(int,input().split())
h=[None]*M
w=[None]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())
c1=collections.Counter(h)
c2=collections.Counter(w)
cnt=0
ans=0
for i in range(len(c1)):
    for j in range(len(c2)):
        for x in range(M):
            flag=True
            if h[x]==c1.most_common()[i][0] and w[x]==c2.most_common()[j][0]:
                ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1]-1)
                flag=False
                break
        if flag:
            ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
h, w, m = map(int, input().split())
L_g = []
L_r = []
L = []
for i in range(m):
    a, b = map(int, input().split())
    L_g.append(a)
    L_r.append(b)
    L.append((a, b))
c1 = collections.Counter(L_g)
c2 = collections.Counter(L_r)

L1 = c1.most_common()
L2 = c2.most_common()

s = L1[0][1]
bL1 = []
for i in range(len(L1)):
    if L1[i][1] == s:
        bL1.append(L1[i])
    else:
        break
s = L2[0][1]
bL2 = []
for i in range(len(L2)):
    if L2[i][1] == s:
        bL2.append(L2[i])
    else:
        break
bL = []
for i in range(len(bL1)):
    for j in range(len(bL2)):
        bL.append((bL1[i][0], bL2[j][0]))
flag = 0
for e in bL:
    if e not in L:
        bom = e
        flag = 1
        break
if flag == 0:
    bom = bL[0]

t = L1[0][1]+L2[0][1]

for e in L:
    if e == bom:
        t -= 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import collections
#import math




#f = open('./input_E.txt')
#
#H,W,M=map(int, f.readline().split())
#bakuha = []
#bakuha_H=[]
#bakuha_W=[]
#for i in range(M):
#    hh,ww=map(int, f.readline().split())
#    bakuha_H.append(hh)
#    bakuha_W.append(ww)
#    bakuha.append([hh,ww])



#
H,W,M=map(int, input().split())
bakuha = []
bakuha_H=[]
bakuha_W=[]
for i in range(M):
    hh,ww=map(int, input().split())
    bakuha_H.append(hh)
    bakuha_W.append(ww)
    bakuha.append([hh,ww])





count_H = collections.Counter(bakuha_H)
H_most = count_H.most_common()
H_most_num = H_most[0][1]

H_only_most = [x for x in H_most if x[1]==H_most_num]
H_kouho = [x[0] for x in H_only_most]


count_W = collections.Counter(bakuha_W)
W_most = count_W.most_common()
W_most_num = W_most[0][1]

W_only_most = [x for x in W_most if x[1]==W_most_num]
W_kouho = [x[0] for x in W_only_most]

ans = H_most_num + W_most_num


kouho = [x for x in bakuha if x[0] in H_kouho and x[1] in W_kouho]

if len(kouho) == len(H_kouho)*len(W_kouho):
    ans-=1

#ryouhou = 0
#for bb in bakuha:
#    x,y = bb
#    if x in H_kouho and y in W_kouho:
#        ryouhou+=1
#
#h_by_w = len(H_kouho)*len(W_kouho)
#
#if ryouhou == h_by_w:
#    ans -= 1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dh=defaultdict(int)
dw=defaultdict(int)
nomap=[]

for _ in range(M):
    h,w=map(int,input().split())
    dh[h]+=1
    dw[w]+=1
    nomap.append([h,w])

goal=0
dhk=list(dh.keys())
dwk=list(dw.keys())


for i in dhk:
    for j in dwk:
        if [i,j] not in nomap:
            if dh[i]+dw[j]>goal:
                goal=dh[i]+dw[j]
        else:
            if dh[i]+dw[j]-1>goal:
                goal=dh[i]+dw[j]-1

print(goal)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
t = list(list(map(int,input().split())) for _ in range(m))

ans = 0

for i in range(h):
  for j in range(w):
    n = [l[0] for l in t].count(i+1) +  [l[1] for l in t].count(j+1)
    if [i+1,j+1] in t:
      n -= 1
    if n > ans:
      ans = n
      
print(ans)

Submission status: Time Limit Exceeded

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


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

A=[]
B=[]
for i in range(h):
    a=0
    for j in range(m):
        if i+1==X[j][0]:
            a+=1
    A.append(a)

A1=[i for i, v in enumerate(A) if v == max(A)]
for i in range(w):
    b=0
    for j in range(m):
        if i+1==X[j][1]:
            b+=1
    B.append(b)

B1=[i for i, v in enumerate(B) if v == max(B)]

Y=[]
for i in range(len(A1)):
    for j in range(len(B1)):
        Y.append([A1[i]+1,B1[j]+1])
        

ans=max(A)+max(B)

Z=[]
for i in range(len(Y)):
    for j in range(m):
        if Y[i]==X[j]:
            Z.append(Y[i])

if Z==Y: print(ans-1)
else : print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,m=map(int,input().split())
hs=[0 for i in range(H)]
ws=[0 for i in range(W)]
M=[[0 for i in range(W)] for j in range(H)]
for i in range(m):
    h,w=map(int,input().split())
    M[h-1][w-1]=1
    hs[h-1]+=1
    ws[w-1]+=1
target_h=hs.index(max(hs))
target_w=ws.index(max(ws))
ans1=0
ans2=0
for i in range(W):
    if ws[i]==max(ws):
        ans10=0
        if max(ws)!=1:
            if M[target_h][i]==1:
                ans10=max(hs)+max(ws)-1
            else:
                ans10=max(hs)+max(ws)
        else:
            if M[target_h][i]==1:
                ans10=max(hs)
            else:
                ans10=max(hs)+1
        ans1=max(ans1,ans10)

for i in range(H):
    if hs[i]==max(hs):
        ans20=0
        if max(hs)!=1:
            if M[i][target_w]==1:
                ans20=max(hs)+max(ws)-1
            else:
                ans20=max(hs)+max(ws)
        else:
            if M[i][target_w]==1:
                ans20=max(ws)
            else:
                ans20=max(ws)+1
        ans2=max(ans2,ans20)
print(max(ans1,ans2))

Submission status: Time Limit Exceeded

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

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1
    
MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]

import itertools
X = list(itertools.product(h_list, w_list))

ans = MAX_h+MAX_w
check = 0

if len(X)<=3*10**5:
    for i in range(M):
        if (h[i],w[i]) in X:
            check += 1

if len(X)==check:
    ans -= 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

h,w,m = map(int, input().split(" "))
bombs = [[] for i in range(m)]
for i in range(m):
  bombs[i] = tuple(map(int, input().split(" ")))

row_count = [[i+1,0] for i in range(h)]
col_count = [[i+1,0] for i in range(w)]
for bomb in bombs:
  row_count[bomb[0]-1][1] += 1
  col_count[bomb[1]-1][1] += 1
  
r_max = max([row[1] for row in row_count])
c_max = max([col[1] for col in col_count])

r_options = [row[0] for row in row_count if row[1]==r_max]
c_options = [col[0] for col in col_count if col[1]==c_max]


b_list = list(itertools.product(r_options, c_options))

if all([b in bombs for b in b_list]):
  print(r_max+c_max-1)
else:
  print(r_max+c_max)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    bc = 0
    h, w, m = map(int, input().split())
    bh = [0]*h
    bw = [0]*w
    b = []
    for _ in range(m):
        ht, wt = map(int, input().split())
        bh[ht-1] += 1
        bw[wt-1] += 1
        b.append([ht,wt])
    bc = max(bh) + max(bw)

    mbh = max(bh)
    mbw = max(bw)
    bhindxes = [i for i, x in enumerate(bh) if x == mbh]
    bwindxes = [i for i, x in enumerate(bw) if x == mbw]
    mb = 0
    tmpmb = 0
    ans = [0,0]
    for mh in bhindxes:
        for mw in bwindxes:
            tmpmb = bh[mh]
            if [mh+1, mw+1] not in b:
                tmpmb += bw[mw]
            if mb < tmpmb:
                ans = [mh, mw]
                mb = tmpmb
    if  [ans[0]+1, ans[1]+1] in b:
        bc -= 1
    print(bc)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
number=list(map(int,input().split()))
H,W,M=number[0],number[1],number[2]
h_count=[0 for i in range(H+1)]
w_count=[0 for i in range(W+1)]
T=[]
ans=[]
flag=0
for i in range(M):
    S=list(map(int,input().split()))
    T.append(S)
    h_count[S[0]]+=1
    w_count[S[1]]+=1
h=max(h_count)
w=max(w_count)
if [h_count.index(h),w_count.index(w)] in T:
    h_count=np.array(h_count)
    w_count=np.array(w_count)
    h_max=[i for i, x in enumerate(h_count) if x == h]
    w_max=[i for i, x in enumerate(w_count) if x == w]
    for i in h_max:
        if flag==1:
            break
        for j in w_max:
            if [i,j] in T:
                pass
            else:
                print(h+w)
                flag=1
                break
    if flag==0:
        print(h+w-1)
else:
    print(int(h+w))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
 
h, w, m = map(int, sys.stdin.readline().split())
hl = []
wl = []
 
for _ in range(m):
    hi, wi = map(int, sys.stdin.readline().split())
    hl.append(hi)
    wl.append(wi)
 
hc = Counter(hl)
wc = Counter(wl)
 
maxh = max(hc.values())
maxw = max(wc.values())
 
seth = []
setw = []
 
for c,num in hc.most_common():
    if num != maxh:
        break
    seth.append(c)
 
for c,num in wc.most_common():
    if num != maxw:
        break
    setw.append(c)
 
ans = 0

zp = list(zip(hl, wl))
 
for hei in seth:
    for wei in setw:
        temp = hc[hei]+wc[wei]
        if (hei, wei) in zp:
            temp -= 1
        ans = max(ans, temp)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict

H, W, M = map(int, input().split())
horizon_set = defaultdict(set)
vertical_set = defaultdict(set)
horizon = defaultdict(int)
vertical = defaultdict(int)
bombs = set()
for _ in range(M):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    horizon_set[y].add(x)
    vertical_set[x].add(y)
    horizon[y] += 1
    vertical[x] += 1
    bombs.add((x, y))

yn = sorted(horizon.items(), key=lambda yn: yn[::-1], reverse=True)
xn = sorted(vertical.items(), key=lambda xn: xn[::-1], reverse=False)
xnn = [n for x, n in xn]
ans = 0
y, ny = yn[0]
for j in range(len(xn)):
    x, nx = xn[j]
    n = nx + ny
    if (x, y) in bombs:
        n -= 1
    ans = max(ans, n)

for i in range(1, len(yn)):
    y, ny = yn[i]

    jm = bisect.bisect_left(xnn, ans - ny)
    for j in range(jm, len(xn)):
        x, nx = xn[j]
        n = nx + ny
        if (x, y) in bombs:
            n -= 1
        ans = max(ans, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
A=list(map(int,input().split()))
a=[]
b=[]
c=[]
yy=[]
xx=[]
x=1
r=1
t=0
res=1
re=1
rex=0
rey=0
for i in range(A[2]):
  N=list(map(int,input().split()))
  a.append(N[0])
  b.append(N[1])
  c.append(N)
while x<=A[0]:
  f=a.count(x)
  if rex<f:
    rex=f
    xx.clear()
    xx.append(x)
  elif rex==f:
    xx.append(x)
  x+=1
while r<=A[1]:
  g=b.count(r)
  if rey<g:
    rey=g
    yy.clear()
    yy.append(r)
  elif rey==g:
    yy.append(r)
  r+=1
for tr in yy:
  for tx in xx:
    q=c.count([tx,tr])
    if q==0:
      res=0
      break
      
re=rey+rex-res

print(re)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W, M = [int(item) for item in input().split()]
    targets = [[int(item) -1 for item in input().split()] for _ in range(M)]

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

    for i,j in targets:
        col[i] += 1
        row[j] += 1

    max_col = max(col)
    max_row = max(row)
    max_col_index = []
    max_row_index = []

    for i in range(H):
        if col[i] == max_col:
            max_col_index.append(i)

    for i in range(W):
        if row[i] == max_row:
            max_row_index.append(i)

    res = 0
    for item in max_col_index:
        for jtem in max_row_index:
            if [item, jtem] in targets:
                res = max(res, max_col + max_row - 1)
            else:
                res = max(res, max_col + max_row)
    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

maxr, maxc = Counter(), Counter()

mass = set()

for i in range(M):
    h, w = map(int, input().split())
    mass.add((h-1, w-1))
    maxr[h-1]+=1
    maxc[w-1]+=1

res = 0

for r in maxr.keys():
    buf = maxr[r]
    for c in maxc.keys():
        res = max(res, buf+maxc[c] - int((r, c) in mass))
print(res)

Submission status: Time Limit Exceeded

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


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

for _ in range(M):
    hi, wi = map(int,input().split())
    listH[hi] += 1
    listW[wi] += 1
    Bom.append((hi,wi))

def find_max(listA):
    indexes = []
    max_value = 0
    for i,a in enumerate(listA):
        if max_value < a:
            indexes = [i]
            max_value = a
        elif max_value == a:
            indexes.append(i)
    return indexes

maxH = find_max(listH)
maxW = find_max(listW)

res = 0
for i in maxH:
    for j in maxW:
        
        if (i,j) in Bom:
            temp = listH[i] + listW[j] - 1
        else:
            temp = listH[i] + listW[j]
        if temp > res:
            res = temp

print(res)

Submission status: Time Limit Exceeded

Solution code:
A=list(map(int,input().split()))
a=[]
b=[]
c=[]
yy=[]
xx=[]
x=1
r=1
t=0
res=1
re=1
rex=0
rey=0
for i in range(A[2]):
  N=list(map(int,input().split()))
  a.append(N[0])
  b.append(N[1])
  c.append(N)
while x<=A[0]:
  f=a.count(x)
  if rex<f:
    rex=f
    xx.clear()
    xx.append(x)
  elif rex==f:
    xx.append(x)
  x+=1
while r<=A[1]:
  g=b.count(r)
  if rey<g:
    rey=g
    yy.clear()
    yy.append(r)
  elif rey==g:
    yy.append(r)
  r+=1
for tr in yy:
  for tx in xx:
    q=c.count([tx,tr])
    if q==0:
      res=0
      break
      
re=rey+rex-res

print(re)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [list(map(int, input().split())) for _ in range(M)]
bomb = [[0]*W for _ in range(H)]
for i in range(M):
    bomb[h[i][0]-1][h[i][1]-1] += 1

Hnum = [0]*H
Wnum = [0]*W
for i in range(H):
    for j in range(W):
        if bomb[i][j] == 1:
            Hnum[i] += 1
            Wnum[j] += 1

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, Hnum[i] + Wnum[j] - bomb[i][j])

print(str(ans))

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

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

ctr_h = defaultdict(list)
ctr_w = defaultdict(list)

for h, w in X:
    ctr_h[h].append((h, w))
    ctr_w[w].append((h, w))

val_h = sorted(ctr_h.items(), key=lambda x: -len(x[1]))
val_w = sorted(ctr_w.items(), key=lambda x: -len(x[1]))

max_h = len(val_h[0][1])
max_w = len(val_w[0][1])

res = 0
for h, pairs_h in val_h:
    if len(pairs_h) < max_h:
        break

    for w, pairs_w in val_w:
        if len(pairs_w) < max_w:
            break

        cand = set()
        for point in pairs_h:
            cand.add(point)

        for point in pairs_w:
            cand.add(point)

        res = max(res, len(cand))

print(res)