Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

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

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

1 \leq h_i \leq H

1 \leq w_i \leq W

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

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

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

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

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

Sample Output 3

6



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


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import itertools
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = []
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw.append(str(h-1)+"_"+str(w-1))

hmax_ind = list(map(lambda x: True if x == max(Hsum) else False, Hsum))
hmax_ind = list(itertools.compress(range(len(Hsum)), hmax_ind))
wmax_ind = list(map(lambda x: True if x == max(Wsum) else False, Wsum))
wmax_ind = list(itertools.compress(range(len(Wsum)), wmax_ind))

fi = 0
for h in hmax_ind:
  for w in wmax_ind:
    if str(h)+"_"+str(w) not in hw:
      fi = 1
if fi == 1:
  print(max(Hsum) + max(Wsum))
else:
  print(max(Hsum) + max(Wsum)-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int,input().split())
S1 = [0 for i in range(H)]
S2 = [0 for i in range(W)]
bombs_list = []

for i in range(M):
  hi, wi = map(int,input().split())
  bombs_list.append([hi-1, wi-1])
  S1[hi-1] += 1
  S2[wi-1] += 1

S1max = max(S1)
S1max_index = [i for i, x in enumerate(S1) if x == S1max]
S2max = max(S2)
S2max_index = [i for i, x in enumerate(S2) if x == S2max]
bombs = S1max + S2max
Sindex = []
for i in range(len(S1max_index)):
  for j in range(len(S2max_index)):
    Sindex.append([S1max_index[i], S2max_index[j]])

for i in range(len(bombs_list)):
  if bombs_list[i] in Sindex:
    Sindex.remove(bombs_list[i])
    if len(Sindex) == 0:
      bombs -= 1
      break
print(bombs)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as ddict

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

rows=ddict(int)
cols=ddict(int)

ii=jj=0
ia,ja=[],[]
for i,j in tgts:
    rows[i]+=1
    cols[j]+=1
    x=rows[i]
    if x>ii:
        ii=x
        ia=[i]
    elif x==ii:
        ia.append(i)
    y=cols[j]
    if y>jj:
        jj=y
        ja=[j]
    elif y==jj:
        ja.append(j)



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:
h,w,m = map(int, input().split())
retu = [0 for i in range(h)]
gyou = [0 for  i in range(w)]
h_max = 0
w_max = 0
bom = [[0 for i in range(h)] for j in range(w)]
h_li =  []
w_li = []
for i in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    bom[wi][hi] = 1
    retu[hi] += 1
    gyou[wi] += 1
    if retu[hi] > h_max:
        h_max = retu[hi]
        h_li = [hi]
    elif retu[hi] == h_max:
        h_li.append(hi)
    if gyou[wi] > w_max:
        w_max = gyou[wi]
        w_li = [wi]
    elif gyou[wi] == w_max:
        w_li.append(wi)
ans = h_max + w_max -1
for i in range(len(h_li)):
    for j in range(len(w_li)):
        if bom[w_li[j]][h_li[i]] == 0:
            ans += 1
            break
        else:
            continue
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
L = [[0 for _ in range(W)] for _ in range(H)]
for i in range(M):
    h,w = map(int,input().split())
    L[h-1][w-1] += 1
y = 0
yy = 0
yl = []
t = 0
tt = 0
tl = []
for i in range(H):
    a = sum(L[i])
    if a > y:
        y = a
        yy = i
        yl = [i]
    elif a == y:
        yl.append(i)
R = list(zip(*L))
for i in range(W):
    b = sum(R[i])
    if b > t:
        t = b
        tt = i
        tl = [i]
    elif b == t:
        tl.append(i)
if len(yl) == 1 and len(tl) != 1:
    for i in range(len(tl)):
        if L[yy][tl[i]] == 0:
            tt = tl[i]
            break
elif len(tl) == 1 and len(yl) != 1:
    for i in range(len(yl)):
        if L[yl[i]][tt] == 0:
            yy = yl[i]
elif len(yl) != 1 and len(tl) != 1:
    for i in range(len(yl)):
        for j in range(len(tl)):
            if L[yl[i]][tl[j]] == 0:
                yy = yl[i]
                tt = tl[j]
if L[yy][tt] == 1:
    print(y + t - 1)
else:
    print(y + t)

Submission status: Time Limit Exceeded

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

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

hl = []
for i in range(H):
  hl.append(h.count(i+1))

wl = []
for i in range(W):
  wl.append(w.count(i+1))

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

if hmax>=wmax:
  x = hl.index(hmax) + 1
  w2 = []
  for i in range(M):
    if h[i]!=x:
      w2.append(w[i])
  wl = []
  for i in range(W):
    wl.append(w2.count(i+1))
  wmax = max(wl)
else:
  y = wl.index(wmax) + 1
  h2 = []
  for i in range(M):
    if w[i]!=y:
      h2.append(h[i])
  hl = []
  for i in range(H):
    hl.append(h2.count(i+1))
  hmax = max(hl)

print(hmax + wmax)

Submission status: Time Limit Exceeded

Solution code:
H , W , M = map(int,input().split())
h = [0]*M
w = [0]*M
for i in range(M):
  h[i] , w[i] = map(int,input().split())
G1 = [0]*H
G2 = [0]*W
for i in range(M):
  temp = h[i] - 1
  G1[temp] += 1
for  i in range(M):
  temp = w[i] - 1
  G2[temp] += 1
G3 = [[h[i] - 1 , w[i] - 1] for i in range(M)]
M1 = max(G1)
M2 = max(G2)
M1L = []
M2L = []
for i in range(H):
  if G1[i] == M1:
    M1L.append(i)
for j in range(W):
  if G2[j] == M2:
    M2L.append(j)
c = 0
for i in M1L:
  for j in M2L:
    if [i,j] not in G3:
      c = 1
      break
  if c ==1:
    break
if c == 1:
  print(M1 + M2)
else:
  print(M1 + M2 - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
  h1,w1=map(int,input().split())
  l[h1-1][w1-1]=1
  lh[h1-1]+=1
  lw[w1-1]+=1
hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    lw2.append(i)
 
s=1
for m in lh2:
  for m2 in lw2:
    if l[m][m2]==0:
      s=0
      
print(hmax+wmax-s)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())
bomb = list(list(map(int, input().split())) for num in range(M))
maxn = 0
test = 0
for i in range (H):
  for j in range (W):
    test = 0
    for num in range (M):
      if (i == bomb[num][0] - 1  or j == bomb[num][1] - 1):
        test+=1
    if (test > maxn):
      maxn = test
      
      
print(maxn)

Submission status: Time Limit Exceeded

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

h_list = []
w_list = []
hw_list = []

for m in range(M):
    h_buf, w_buf = map(int, input().split())
    h_list.append(h_buf)
    w_list.append(w_buf)
    hw_list.append([h_buf, w_buf])

h_c = collections.Counter(h_list)
w_c = collections.Counter(w_list)

M = 0
count_h = 0
count_w = 0
M_j = 0
finish = 0

for l in h_c.most_common():
    if (count_h > l[1])|(finish == 1): break
    count_h = l[1]
    i = l[0]
    M_i = count_h
    for s in w_c.most_common():
        if (count_w > s[1])|(finish == 1): break
        count_w = s[1]
        j = s[0]
        M_buf = count_w
        if [i,j] in hw_list:
            M_buf -= 1
        else:
            finish = 1
        if M_buf>M_j:
            M_j = M_buf

print(M_i + M_j)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    regy = [0]*h
    regx = [0]*w
    for x in s:
        regy[x[0]] += 1
        regx[x[1]] += 1
    maxy = 0
    indy = []
    for i in range(h):
        if maxy < regy[i]:
            indy = [i]
            maxy = regy[i]
        elif maxy == regy[i]:
            indy.append(i)
    maxx = 0
    indx = []
    for i in range(w):
        if maxx < regx[i]:
            indx = [i]
            maxx = regx[i]
        elif maxx == regx[i]:
            indx.append(i)

    ans = maxy + maxx
    tmp = 1
    for y in indy:
        for x in indx:
            if [y, x] not in s[:]:
               tmp = 0
    print(ans - tmp)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy
h,w,m=map(int,input().split())
h_arr=[0]*h
w_arr=[0]*w
record = set()
for i in range(m):
    tmp_h, tmp_w = map(int,input().split())
    record.add((tmp_h,tmp_w))
    h_arr[tmp_h-1] += 1
    w_arr[tmp_w-1] += 1
#最大の列と行の交差点に爆破対象があるかどうかがわからない?
max_h_indexes = [i for i, x in enumerate(h_arr) if x == max(h_arr)]
max_w_indexes = [i for i, x in enumerate(w_arr) if x == max(w_arr)]
ans = max(h_arr) + max(w_arr) -1
for i in max_h_indexes:
    for j in max_w_indexes:
        if not((i+1,j+1) in record):
            ans += 1
            break
        else:
            continue
    break
print(ans)

Submission status: Time Limit Exceeded

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

# Input#
# n = int(input())
h, w, m = map(int, input().split())
tar_list = []

h_count = [0] * (h + 1)
w_count = [0] * (w + 1)

h_max = 0
w_max = 0

h_maxlist = []
w_maxlist = []

ans = 0
ans_tmp = 0

for i in range(m):
    h_in, w_in = map(int, input().split())
    tar_list.append((h_in, w_in))

    h_count[h_in] += 1
    if h_count[h_in] > h_max:
        h_max = h_count[h_in]
        h_maxlist = [h_in]
    elif h_count[h_in] == h_max:
        h_maxlist.append(h_in)

    w_count[w_in] += 1
    if w_count[w_in] > w_max:
        w_max = w_count[w_in]
        w_maxlist = [w_in]
    elif w_count[w_in] == w_max:
        w_maxlist.append(w_in)


for i in range(len(h_maxlist)):
    tar_h = h_maxlist[i]
    if h_count[tar_h] == h_max:
        for j in range(len(w_maxlist)):
            tar_w = w_maxlist[j]
            if w_count[tar_w] == w_max:
                if (tar_h, tar_w) in tar_list:
                    ans_tmp = h_count[tar_h] + w_count[tar_w] - 1
                    ans = max(ans, ans_tmp)
                else:
                    ans_tmp = h_count[tar_h] + w_count[tar_w]
                    ans = max(ans, ans_tmp)


print("{}".format(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)]
a=[0 for i in range(h+1)]
b=[0 for _ in range(w+1)]
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a)
bm=max(b)
aa=[i for i, x in enumerate(a) if x==am]
bb=[i for i, x in enumerate(b) if x==bm]
for i in aa:
    for j in bb:
        if [i,j] in bomb:
            continue
        else:
            print(am+bm)
            exit()
print(am+bm-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

bomb_h = [0] * H
bomb_w = [0] * W
grid = [[False] * W for _ in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    grid[h-1][w-1] = True

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if not grid[h][w]:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w,m=map(int,input().split())
    target=[tuple(map(int,input().split())) for i in range(m)]
    lines=[0]*w
    rows=[0]*h
    for th,tw in target:
        lines[tw-1]+=1
        rows[th-1]+=1
    max_lines=max(lines)
    max_rows=max(rows)
    max_wi=[i for i,wi in enumerate(lines) if wi==max_lines]
    max_hi=[i for i,hi in enumerate(rows) if hi==max_rows]
    flag=[]
    for wi in max_wi:
        for hi in max_hi:
            if (hi+1,wi+1) in target:
                flag.append(-1)
            else:
                flag.append(0)
    # print(max_rows,max_hi,max_lines,max_wi,flag)
    ans=max_lines+max_rows+max(flag)
    return ans

if __name__=='__main__':
    ans=main()
    print(ans)

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = [[False] * w for _ in range(h)]
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[y][x] = True
        
    kouho_h = []
    for i in range(h):
        if cnt_h[i] == max(cnt_h):
            kouho_h.append(i)
    kouho_w = []
    for i in range(w):
        if cnt_w[i] == max(cnt_w):
            kouho_w.append(i)
    
    flag = False
    for i in kouho_h:
        for j in kouho_w:
            if bomb[i][j] == False:
                flag = True
                break
    if flag:
        print(max(cnt_h) + max(cnt_w))
    else:
        print(max(cnt_h) + max(cnt_w) - 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
MAP=[[0 for _ in range(w)] for _ in range(h)]
count = 0
for _ in range(m):
  h1,w1=map(int,input().split())
  MAP[h1-1][w1-1]=1
c=[sum(i) for i in list(zip(*MAP))]
d=0
for i in range(h):
  for j in range(w):
    if MAP[i][j]==1:
      d=max(d,sum(MAP[i])+c[j]-1)
    else:
      d=max(d,sum(MAP[i])+c[j])
print(d)

Submission status: Time Limit Exceeded

Solution code:

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

mp = []
hp = [0] * h
wp = [0] * w

for i in range(m):
    l = list(map(int, input().split()))
    mp.append(l)
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1

hpdex = [i for i, x in enumerate(hp) if x == max(hp)]
wpdex = [i for i, x in enumerate(wp) if x == max(wp)]

for i in range(len(hpdex)):
    for j in range(len(wpdex)):
        if [hpdex[i] + 1, wpdex[j] + 1] not in mp:
            print(max(hp) + max(wp))
            exit()

print(max(hp) + max(wp) - 1)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
hw = []
hs = [0]*(h+1)
ws = [0]*(w+1)
for _ in range(m):
  x, y = map(int, input().split())
  hw.append((x, y))
  hs[x] += 1
  ws[y] += 1

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

Submission status: Time Limit Exceeded

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

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

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

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_keys = [k for k, v in h_counter]
w_keys = [k for k, v in w_counter]

ans = 0
highest = h_counter[0][1] + w_counter[0][1]
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        ret = highest - ((hk, wk) in targets)
        ans = max(ans, ret)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
r=[0]*(n+1)
c=[0]*(m+1)
l=[]
for _ in range(k):
  a,b=map(int,input().split())
  l.append([a,b])
  r[a]+=1
  c[b]+=1
m1=max(r)
x=[]
for i in range(n+1):
  if(r[i]==m1):
    x.append(i)
m2=max(c)
y=[]
for i in range(m+1):
  if(c[i]==m2):
    y.append(i)
ans=m1+m2
z=0
for i in x:
  for j in y:
    if([i,j] not in l):
      z=-1
      break
if(z==0):
  print(ans-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
##
for _ in range(1):
    r,c,m=cin()
    d=dd(list)
    ro=[0]*r
    co=[0]*c
    for i in range(m):
        x,y=cin()
        ro[x-1]+=1
        co[y-1]+=1
        d[x-1]+=[y-1]

    ans=0
    mar=[];mac=[]
    mar1=max(ro);mac1=max(co);
    for i in range(r):
        if(ro[i]==mar1):
            mar+=[i]
    for i in range(c):
        if(co[i]==mac1):
            mac+=[i]
##    print(mar ,mac)
    for i in mar:
        for j in mac:
            t=0
            if(j in d[i]):t=-1
            ans=max(ans,ro[i]+co[j]+t)
    print(ans)
    
    
    
    
    

                    
                
    

    

        


    
        

    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
import sys
h,w,m = (int(x) for x in input().split())
hw = []
for _ in range(m):
    hw.append([int(x) for x in input().split()])

np_hw = np.array(hw)

c_h = collections.Counter(np_hw[:,0])
c_w = collections.Counter(np_hw[:,1])

max_h_list = []
max_w_list = []
for i in range(len(c_h)):
    if c_h.most_common()[i][1] == c_h.most_common()[0][1]:
        max_h_list.append(c_h.most_common()[i][0])
for i in range(len(c_w)):
    if c_w.most_common()[i][1] == c_w.most_common()[0][1]:
        max_w_list.append(c_w.most_common()[i][0])

ans = c_h.most_common()[0][1]+c_w.most_common()[0][1]-1
for i in max_h_list:
    for j in max_w_list:
        if [i,j] not in hw:
            ans += 1
            print(ans)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
ch,cw = [0 for i in range(H)],[0 for i in range(W)]
mapp = [[0 for i in range(H)] for i in range(W)]
h,w = [0 for i in range(M)],[0 for i in range(M)]
for i in range(M):
    h[i],w[i] = map(int,input().split())
    ch[h[i]-1] += 1
    cw[w[i]-1] += 1
    mapp[w[i]-1][h[i]-1]=1



mh = max(ch)
mw = max(cw)

fh = []
fw = []

for i in range(H):
    if ch[i] == mh:
        fh.append(i)

for i in range(W):
    if cw[i] == mw:
        fw.append(i)

r = mw+mh-1

m = len(fw)*len(fh)

for i in range(M):
    if h[i]-1 in fh:
        if w[i]-1 in fw:
            m = m-1

if m>0:
    r += 1

print(r)

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

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

h_dict = dict()
w_dict = dict()

targets = list()

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

    h_dict[temp_h] = h_dict.get(temp_h, default=0) + 1
    w_dict[temp_w] = w_dict.get(temp_w, default=0) + 1

    targets.append((temp_h, temp_w))

max_h = max(h_dict.values())
max_w = max(w_dict.values())

h_candidates = [k for k, v in h_dict.items() if v == max_h]
w_candidates = [k for k, v in w_dict.items() if v == max_w]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
from collections import deque

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

hw = [list(map(int, input().split())) for i in range(m)]

hw.sort()
hw_rev = sorted(hw, key=lambda x: x[1])

index_sum_h = []
sum_h = []
index = -1
for i in hw:
    a, b = i
    if a == index:
        index_sum_h[-1][1] += 1
    else:
        index = a
        index_sum_h.append([a, 1])

index_sum_w = []
index = -1
for i in hw_rev:
    a, b = i
    if b == index:
        index_sum_w[-1][1] += 1
    else:
        index = b
        index_sum_w.append([b, 1])

# print(hw)
# print(index_sum_h)
# print(index_sum_w)

index_sum_h = sorted(index_sum_h, key=lambda x: x[1], reverse=True)
index_sum_w = sorted(index_sum_w, key=lambda x: x[1], reverse=True)

# print(index_sum_h)
# print(index_sum_w)
dq = deque([[0, 0]])

ans_tmp = index_sum_h[0][1]+index_sum_w[0][1]
while len(dq) > 0:
    index_h, index_w = dq.popleft()
    a, b = index_sum_h[index_h]
    c, d = index_sum_w[index_w]

    # print([a, c])
    # print([a, c] in hw)
    if [a, c] in hw:
        ans = ans_tmp-1
        if index_h+1 < len(index_sum_h):
            if index_sum_h[index_h+1][1] == b:
                dq.append([index_h+1, index_w])
        if index_w+1 < len(index_sum_w):
            if index_sum_w[index_w+1][1] == d:
                dq.append([index_h, index_w+1])

    else:
        print(b+d)
        exit()

print(ans)

Submission status: Time Limit Exceeded

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

r,c,m=map(int,input().split())
q=[list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
M=[[0 for i in range(c)] for _ in range(r)]
for i,j in q:
    M[i][j]=1

rows = [0]*r
cols = [0]*c

for i in range(r):
    rows[i]=sum(M[i])

for i in range(c):
    A = [M[j][i] for j in range(r)]
    cols[i] = sum(A)


#print(rows,cols)
MAX = 0
for i in range(r):
    for j in range(c):
        if M[i][j]==1:
            MAX = max(MAX,rows[i]+cols[j]-1)
        else:
            MAX = max(MAX,rows[i]+cols[j])
print(MAX)

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
h_max=max(h_list)
w_max=max(w_list)
h_max_list=[]
w_max_list=[]
for i in range(h) :
  if h_list[i]==h_max :
    h_max_list.append(i)

for i in range(w) :
  if w_list[i]==w_max :
    w_max_list.append(i)
flag=False
for i in h_max_list :
  for j in w_max_list :
    if hw_list[i][j]!=1 :
      flag=True
      break

if flag :
  print(str(h_max+w_max))
else :
  print(str(h_max+w_max-1))

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
S = [[0 for _ in range(w)] for _ in range(h)]
count_h = [0 for _ in range(h)]
count_w = [0 for _ in range(w)]
for _ in range(m):
    i,j = map(int,input().split());i-=1;j-=1
    S[i][j] = 1
    count_h[i]+=1; count_w[j] +=1
max_h = max(count_h);max_w = max(count_w)
ind_h = []
for i in range(h):
    if count_h[i] == max_h:
        ind_h.append(i)
        
ind_w = []
for j in range(w):
    if count_w[j] == max_w:
        ind_w.append(j)

flag = 0
for i in ind_h:
    for j in ind_w:
        if S[i][j]==0:
            flag = 1
            
if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w-1)

Submission status: Time Limit Exceeded

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

def main():
    H, W, M = map(int, input().split())
    bomb = [list(map(int, input().split()))for i in range(M)]
    H_bomb = [0] * (H + 1)
    W_bomb = [0] * (W + 1)
    for b in bomb:
        H_bomb[b[0]] += 1
        W_bomb[b[1]] += 1
    ans = max(H_bomb) + max(W_bomb)
    H_bomb_index = [i for i, v in enumerate(H_bomb) if v == max(H_bomb)]
    W_bomb_index = [i for i, v in enumerate(W_bomb) if v == max(W_bomb)]
    x_point = []
    for h in H_bomb_index:
        for w in W_bomb_index:
            x_point.append([h, w])
    flag = True
    for x in x_point:
        if x not in bomb:
            flag = False
    if flag:
        ans -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
countH = [[h, 0] for h in range(H)]
countW = [[w, 0] for w in range(W)]
Bh = {}

for i in range(M):
  h, w = map(int, input().split())
  h, w = h-1, w-1
  if h in Bh:
    Bh[h].append(w)
  else:
    Bh[h] = [w]
  countH[h][1] += 1
  countW[w][1] += 1

countH.sort(reverse=True, key=lambda x: x[1])
countW.sort(reverse=True, key=lambda x: x[1])
#print(countH)
#print(countW)
#rint(Bh)

maxh = countH[0][1]
maxw = countW[0][1]
ans = maxh + maxw
ch = [countH[0][0]]
i = 1
while i < H and countH[i][1]==maxh:
  ch.append(countH[i][0])
  i += 1
cw = [countW[0][0]]
i = 1
while i < W and countW[i][1]==maxw:
  cw.append(countW[i][0])
  i += 1
flag = False
for h in ch:
  for w in cw:
    #print(h,w)
    if h not in Bh or w not in Bh[h]:
      flag = True
if flag:
  print(ans)
else:
  print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, M = map(int, input().split())
field = np.array([[0 for _ in range(W)] for _ in range(H)])

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

wsum = field.sum(axis=0)
hsum = field.sum(axis=1)

wsum_max = wsum.max()
hsum_max = hsum.max()

wsum_max_id = np.where(hsum == hsum.max())[0]
hsum_max_id = np.where(wsum == wsum.max())[0]

flag = True

for h in wsum_max_id:
  if [w for w in range(W) if field[h][w] == 0 and (w in hsum_max_id)]:
    print(wsum_max + hsum_max)
    flag = False
    break
if flag:
  print(wsum_max + hsum_max - 1)

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).most_common()
wc = Counter(wl).most_common()

maxh = hc[0][1]
maxw = wc[0][1]

seth = []
setw = []

for c,num in hc:
    if num != maxh:
        break
    seth.append(c)

for c,num in wc:
    if num != maxw:
        break
    setw.append(c)

ans = 0

def cnt(r, c):
    for j in range(m):
        if hl[j] == r and wl[j] == c:

            return -1
    return 0

for hei in seth:
    for wei in setw:
        ans = max(ans, hl.count(hei)+wl.count(wei)+cnt(hei, wei))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    h,w,m  = map(int, input().split())
    hm = [0]*m
    wm=[0]*m
    hw = [[0 for i in range(w+1)] for j in range(h+1)]
    for i in range(m):
        hm[i], wm[i] = map(int, input().split())
        hw[hm[i]][wm[i]]=1

    ww=[0]*(h+1)
    hh=[0]*(w+1)
    for i in range(m):
        ww[hm[i]]+=1
    for i in range(m):
        hh[wm[i]]+=1

    hmax=max(ww)
    wmax=max(hh)

    hichi=[i for i, v in enumerate(ww) if v == hmax]
    wichi=[i for i, v in enumerate(hh) if v == wmax]

    ch=1
    for i in hichi:
        for j in wichi:
            if hw[i][j]==0:
                ch=0



    print(hmax+wmax-ch)
resolve()

Submission status: Time Limit Exceeded

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

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

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

h_max_idx = []
w_max_idx = []

if len(h_max_idx)>=10**3:
    h_max_idx = h_max_idx[:10**3]
if len(w_max_idx)>=10**3:
    w_max_idx = w_max_idx[:10**3]

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

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

# print(h_max_idx)
# print(w_max_idx)

if len(h_max_idx)>=10**3:
    h_max_idx = h_max_idx[:10**3]
if len(w_max_idx)>=10**3:
    w_max_idx = w_max_idx[:10**3]

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,M=map(int,input().split())
h=[0]*H
w=[0]*W
xy=[]
for i in range(M):
    x,y=map(int,input().split())
    xy.append([x,y])
    h[x-1]+=1
    w[y-1]+=1
ans=max(h)+max(w)
hm=list(*np.where(h == np.max(h)))
wm=list(*np.where(w == np.max(w)))
for n in hm:
    for m in wm:
        for j in range(M):
            x = xy[j][0]
            y = xy[j][1]
            if x == n + 1 and y == m + 1:
                break
        else:
            print(ans)
            exit()
print(ans-1)

Submission status: Time Limit Exceeded

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

max = 0
for i in range(1, h+1):
  for j in range(1, w+1):
    count = 0
    for k in l:
      if k[0] == i or k[1] == j:
        count += 1
    if count > max:
      max = count

print(max)