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())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
dp = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
    hh, ww = map(int, input().split())
    w[ww - 1] += 1
    dp[hh - 1][ww - 1] += 1

for i in range(H):
    h[i] = sum(dp[i])

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0


for i in hhhh:
    if check == 1:
        break
    for j in wwww:
        if dp[i][j] == 0:
            check = 1
            break
print(hhh + www - (1 - check))

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
points = []
xs = {}
ys = {}
for i in range(m):
    x,y = map(int,input().split())
    points.append([x,y])
    if xs.get(str(x)):
        xs[str(x)] += 1
    else:
        xs[str(x)] = 1
    if ys.get(str(y)):
        ys[str(y)] += 1
    else:
        ys[str(y)] = 1
max_x = [k for k, v in xs.items() if v == max(xs.values())]
max_y = [k for k, v in ys.items() if v == max(ys.values())]
boolen = 0
for x in max_x:
    for y in max_y:
        if [int(x), int(y)] not in points:
            boolen = 1
            break
if boolen == 0:
    print(xs[max_x[0]] + ys[max_y[0]]-1)
else:
    print(xs[max_x[0]] + ys[max_y[0]])

Submission status: Time Limit Exceeded

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

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence
import copy

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    maxRowCount = 0
    maxRowIndexList: List[int] = []
    tempCodList = copy.deepcopy(codList)
    for row in range(H):
        hitList = list(filter(lambda x: x[0] == row + 1, tempCodList))
        for hit in hitList:
            tempCodList.remove(hit)

        counter = len(hitList)
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    tempCodList = copy.deepcopy(codList)
    for column in range(W):
        hitList = list(filter(lambda x: x[1] == column + 1, tempCodList))
        for hit in hitList:
            tempCodList.remove(hit)
        counter = len(hitList)
        if counter > maxColumnCount:
            maxColumnCount = counter
            maxColumnIndexList = [column + 1]
        elif counter == maxColumnCount:
            maxColumnIndexList.append(column + 1)

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

    print(result - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
h, w, m = map(int, input().split())

h_dic = dd(set)
w_dic = dd(set)

for i in range(m):
    h_c, w_c = map(int, input().split())
    h_dic[h_c].add(i)
    w_dic[w_c].add(i)
#print(h_dic, w_dic)

max_counter = 0
for i in h_dic.keys():
    for j in w_dic.keys():
        counter = len(h_dic[i] | w_dic[j])
        #print(i, j, h_dic[i] | w_dic[j],counter)
        max_counter = max(max_counter, counter)
print(max_counter)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = [int(x) for x in input().split()]
bomb = []
grid = []
for i in range(m):
    bomb.append([int(x)-1 for x in input().split()])
for i in range(h):
    grid.append([0 for x in range(w)])
for b in bomb:
    for i in range(w):
        grid[b[0]][i] += 1
    for i in range(h):
        if i == b[0]:
            continue
        grid[i][b[1]] += 1
max_h = grid.index(max(grid))
max_w = grid[max_h].index(max(grid[max_h]))
print(max(grid[max_h]))

Submission status: Time Limit Exceeded

Solution code:
def argmax_poss(xs):
    max_value = max(xs)
    out = []
    for i in range(len(xs)):
        if xs[i] == max_value:
            out.append(i)
    return(out)

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

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = []

for i in range(m):
  h,w = map(int,input().split())
  record.append((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h_poss = argmax_poss(h_scores)
max_w_poss = argmax_poss(w_scores)

out_pos_count = 0 

for item in record:
    if item[0] in max_h_poss and item[1] in max_w_poss:
        out_pos_count += 1

if len(max_h_poss) * len(max_w_poss) > out_pos_count:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
T = [0] * M
H_cnt = {}
W_cnt = {}
HW = {}
for i in range(M):
    h,w = map(int,input().split())
    if not h in H_cnt:
        H_cnt[h] = 0
    if not w in W_cnt:
        W_cnt[w] = 0
    H_cnt[h] += 1
    W_cnt[w] += 1
    HW[(h,w)] = 1

HL = [[h,cnt] for h,cnt in H_cnt.items()]
WL = [[w,cnt] for w,cnt in W_cnt.items()]

HL.sort(key=lambda x: x[1],reverse=True)
WL.sort(key=lambda x: x[1],reverse=True)

HS = []
max_cnt = 0
for h,cnt in HL:
    if max_cnt<=cnt:
        HS.append([h,cnt])
        continue
    break

WS = []
max_cnt = 0
for w,cnt in WL:
    if max_cnt<=cnt:
        WS.append([w,cnt])
        continue
    break

cnt = 0
ans = 0
for h,hcnt in HS:
    for w,wcnt in WS:
        if (h,w) in HW:
            cnt = hcnt+wcnt-1
            ans = max(ans,cnt)
            continue
        cnt = hcnt+wcnt
        ans = max(ans,cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, M = map(int, input().split())
    S = []
    for i in range(M):
        S.append(list(map(int, input().split())))
    sums = 0
    current_top = 0

    for i in range(H):
        for j in range(W):
            sums = 0
            for k in range(len(S)):
                if S[k][0] == i+1 or S[k][1] == j+1:
                    sums += 1
            if sums > current_top:
                current_top = sums
    print(current_top)
    
main()

Submission status: Time Limit Exceeded

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

lows = [[0 for j in range(w)] for i in range(h)]
columns = [[0 for j in range(h)] for i in range(w)]
for l in target:
	lows[l[0] - 1][l[1] - 1] = 1
	columns[l[1] - 1][l[0] - 1] = 1

ans = 0
for i in range(h):
	for j in range(w):
		cnt = lows[i].count(1) + columns[j].count(1)
		if lows[i][j] == 1:
			cnt -= 1
		ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Qe():
    h, w, m = map(int, input().split())
    targets = []
    for i in range(m):
        x, y = map(int, input().split())
        targets.append((x, y))

    c = 0
    for hh in range(1, h + 1):
        for ww in range(1, w + 1):
            s = 0
            for h1, w1 in targets:
                if hh == h1 or ww == w1:
                    s += 1
            if c < s:
                c = s
    print(c)


if __name__ == '__main__':
    Qe()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, M = map(int, input().split())
maze = [[0] * W for i in range(H)]
for i in range(M):
    x, y = map(int, input().split())
    maze[x-1][y-1] = 1

maze = np.array(maze)
X = np.sum(maze, axis=0)
ax = np.where(X == np.max(X))


Y = np.sum(maze, axis=1)
ay = np.where(Y == np.max(Y))

X = X.max()
Y = Y.max()

Q = 0
for i in range(len(ax[0])):
    for j in range(len(ay[0])):
        if maze[ay[0][j]][ax[0][i]] == 0:
            Q = X + Y
    else:
        if Q < X + Y - 1:
            Q = X + Y - 1

print(Q)

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

res = []
for n in itertools.product(hmax_ind, wmax_ind):
  res.append(str(n[0])+"_"+str(n[1]))

if len(set(res).intersection(set(hw))) == len(res):
  print(max(Hsum) + max(Wsum)-1)
else:
  print(max(Hsum) + max(Wsum))

Submission status: Time Limit Exceeded

Solution code:

H,W,M=map(int,input().split())
AB=[tuple(map(int,input().split()))for i in range(M)]
AB=[(a-1,b-1)for a,b in AB]
st=set(AB)

Wc=[0]*W
Hc=[0]*H
for a,b in AB:
    Hc[a]+=1
    Wc[b]+=1

ans=0
for i in range(H):
    for j in range(W):
        add = -1 if (i,j) in st else 0
        tmp= Hc[i] + Wc[j] + add
        ans=max(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=[[] for _ in range(h+1)]
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot[x].append(y)   
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
u=0
c=0
for i in a:
    for j in b:
        if j in plot[i]:
            u+=1
        c+=1
ans=x+y
if u==c:
    print(ans-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

max_h=[0 for i in range(h+1)]
max_w=[0 for i in range(w+1)]
grid=[[0 for i in range(w)] for j in range(h)]
pro=[list(map(int,input().split())) for i in range(m)]
pro.sort()
for i in range(m):
    h=pro[i][0]
    w=pro[i][1]
    max_h[h]+=1
    max_w[w]+=1
    grid[h-1][w-1]=1
h_max=[i for i, x in enumerate(max_h) if x == max(max_h)]
w_max=[i for i, x in enumerate(max_w) if x == max(max_w)]

ans=0
for i in h_max:
    for j in w_max:
        cnt=0
        for k in range(h):
            if grid[k][j-1]==1:
                cnt+=1
        
        cnt += grid[i-1].count(1)
        if grid[i-1][j-1]==1:
            cnt -= 1
        
        if cnt > ans:
            ans=cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    H, W, M = map(int, input().split())
    bombs = list(list(map(int, input().split())) for _ in range(M))

    hBucket = [0] * H

    for bomb in bombs:
        hBucket[bomb[0]-1] += 1
    
    rowList = []
    maxBombH = 0

    for i in range(len(hBucket)):
        if hBucket[i] > maxBombH:
            maxBombH = hBucket[i]
            rowList = [i]
        elif hBucket[i] == maxBombH:
            rowList.append(i)
    # print('hBucket: ', hBucket)
    # print('rowList: ', rowList)
    # print('maxBombH: ', maxBombH)
    maxBombW = []

    for row in rowList:
        wBucket = [0] * W
        for bomb in bombs:
            if bomb[0] != row + 1:
                wBucket[bomb[1]-1] += 1
        # print('wBucket: ', wBucket)
        maxBombNum = max(wBucket)
        maxBombW.append(maxBombNum)
    
    print(maxBombH + max(maxBombW))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
line = input().split()
H = int(line[0])
W = int(line[1])
M = int(line[2])

counterH = [0 for i in range(H)]
counterW = [0 for i in range(W)]
Bomb = []

for i in range(M):
  line = input().split()
  Bh = int(line[0])-1
  Bw = int(line[1])-1
  
  Bomb.append([Bh,Bw])
  
  counterH[Bh] = counterH[Bh]+1
  counterW[Bw] = counterW[Bw]+1

maxH = max(counterH)
maxW = max(counterW)
indexH = [i for i,x in enumerate(counterH) if x == maxH]
indexW = [i for i,x in enumerate(counterW) if x == maxW]
#print(indexH,indexW)

for i in indexH:
  for j in indexW:
    if([i,j] in Bomb):
      Dup = 1
    else:
      Dup = 0
      break
  if(Dup == 0):
    break
  

#print(counterH,counterW,Bomb)
print(maxH+maxW-Dup)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=list(map(int, input("").split()))
l=[]
out=0
for i in range(m):
    l.append(list(map(int, input("").split())))
for i in range(1,h+1):
    
    for j in range(1,w+1):
        tf=[False]*m
        for k in range(m):
            if (l[k][0]==i or l[k][1]==j) and tf[k]==False:
                tf[k]=True
        if sum(tf)>out:
            out=sum(tf)
print(out)

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
c1=[sum(i) for i in list(zip(*MAP))]
c2=[sum(i) for i in MAP]
d=[]
for i in range(h):
  for j in range(w):
    d.append(c1[j]+c2[i]-MAP[i][j])
print(max(d))

Submission status: Time Limit Exceeded

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

import numpy as np

listH = np.zeros(H+1)
listW  =np.zeros(W+1) 

for _ in range(M):
    hi, wi = list(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:
        temp = 0
        for obj in Bom:
            if obj[0]==i or obj[1]==j:
                temp += 1
        if temp > res:
            res = temp

print(res)

Submission status: Time Limit Exceeded

Solution code:
def LI():
    return list(map(int,input().split()))

import numpy   
h,w,m=LI()
S=[[0]*w for i in range(h)]
for i in range(m):
    h,w=LI()
    S[h-1][w-1]=1
S=numpy.array(S)
now=0
ind_x=[]
ind_y=[]
Ssumx=[sum(i) for i in S]
SS=S.T
Ssumy=[sum(i) for i in SS]



mx=max(Ssumx)
for i,j in enumerate(Ssumx):
    if j==mx:
        ind_x.append((i,j))
my=max(Ssumy)
for i,j in enumerate(Ssumy):
    if j==my:
        ind_y.append((i,j))
ans=0
for x,numx in ind_x:
    for y,numy in ind_y:
        if S[x][y]==0:
            tmp=numx+numy
        else:
            tmp=numx+numy-1

            
        ans=max(ans,tmp)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comp(v,w):
    if v[0]<w[0] or (v[0]==w[0] and v[1]<w[1]):
        return True
    else:
        return False


def mergesort(list0):
    n=len(list0)
    if n<=1:
        return list0
    else:
        a=mergesort(list0[0:n//2])
        b=mergesort(list0[n//2:n])
        return merge(a,b)


def merge(list1,list2):
    a=0
    b=0
    s=[]
    for c in range(len(list1)+len(list2)):
        if b>=len(list2) or (a<len(list1) and comp(list1[a],list2[b])):
            s.append(list1[a])
            a=a+1
        else:
            s.append(list2[b])
            b=b+1
    return s


h,w,m=map(int,input().split())
g=[]
e1=[[0,t] for t in range(h)]
e2=[[0,t] for t in range(w)]
for c in range(m):
    a,b=map(int,input().split())
    g.append([a-1,b-1])
    e1[a-1][0]+=1
    e2[b-1][0]+=1
f1=mergesort(e1)
f2=mergesort(e2)
p=f1[-1][0]
q=f2[-1][0]
x=[]
y=[]
for c in range(h-1,-1,-1):
    if p>f1[c][0]:
        break
    x.append(f1[c][1])
for c in range(w-1,-1,-1):
    if q>f2[c][0]:
        break
    y.append(f2[c][1])
r=1
for i in x:
    for j in y:
        if not ([i,j] in g):
            r=0
            break
    else:
        continue
    break
print(p+q-r)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = [int(i) for i in input().split()]
Bh = [0]*H
Bw = [0]*W
BB = [[0 for j in range(W)] for i in range(H)]


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

ans = 0
Mh = max(Bh)
Mw = max(Bw)
for i in [i for i, x in enumerate(Bh) if x == Mh]:
    for j in [j for j, x in enumerate(Bw) if x == Mw]:
        ans = max(ans, Mh+Mw-BB[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0
# print([h for h in range(H) if row[h] == r_max])
# print([w for w in range(W) if col[w] == c_max])
for h in [h for h in range(H) if row[h] == r_max]:
    for w in [w for w in range(W) if col[w] == c_max]:
        # print(r_max + c_max - 1 if (h, w) in targets else 0)
        ans = max(ans, r_max + c_max - (1 if (h, w) in targets else 0))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
import numpy as np
H,W,M=map(int,input().split())
arr=np.array([[0 for _ in range(W)] for i in range(H)])
h_arr=[]
w_arr=[]
for _ in range(M):
    h,w=map(int,input().split())
    arr[h-1][w-1]=int(1)
    h_arr.append(h-1)
    w_arr.append(w-1)
h_arr=list(set(h_arr))
w_arr=list(set(w_arr))
ans=0
for i in h_arr:
    for j in w_arr:
        num=np.sum(arr[i,:])+np.sum(arr[:,j])
        if arr[i][j]==1:
            num-=1
        #print(np.sum(arr[i,:]))
        #print(np.sum(arr[:,j]))
        if num>ans:
            ans=num
    
        


#print(arr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
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)

for H in max_h_li:
  for W in max_w_li:
    #print("print([H,W])",[H,W])
    if [H,W] not in hw_grid:
      print(max(h_obj)+max(w_obj))
      sys.exit()
print(max(h_obj)+max(w_obj)-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
isExist = [0 for _ in range(M)]
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    isExist[i] = (h,w)

HMinx = []
WMinx = []

Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax+Wmax
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

flag = False
for i in HMinx:
    for j in WMinx:
        flag2 = False
        for k in isExist:
            if k == (i,j):
                flag2 = True
                break
        if flag2 == False:
            flag = True
            break
    if flag == True:
        break
if flag == True:
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

cells = []
for _ in range(M):
  cells.append(list(map(int, input().split())))

hs = [cell[0] for cell in cells]
ws = [cell[1] for cell in cells]
  
def get_max_cands(hs):
  hs_counter = Counter(hs)
  hs_common = hs_counter.most_common()
  hs_common_count = hs_common[0][1]
  max_row_cands = [hs_counter[0] for hs_counter in hs_common if hs_counter[1] == hs_common_count]
  return {'cands': max_row_cands, 'count': hs_common_count}
               
max_row_cands = get_max_cands(hs)
max_clm_cands = get_max_cands(ws)
            
ans = max_row_cands['count'] + max_clm_cands['count']

for max_row in max_row_cands['cands']:
  for max_clm in max_clm_cands['cands']:
    if [max_row, max_clm] not in cells:
      print(ans)
      exit()
print(ans - 1)

Submission status: Time Limit Exceeded

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

X = [0] * H
Y = [0] * W

A = []
while M:
    M -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    X[x] += 1
    Y[y] += 1

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = False
for i in xms:
    for j in yms:
        if not (i, j) in A:
            ans = True
            break
  
cnt = xm + ym         
print(cnt if ans else cnt - 1)

Submission status: Time Limit Exceeded

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

hlist = [0] * h
wlist = [0] * w
hyou=[]
num_list = []
for i in range(z):
    num_list.append(list(map(int,input().split())))
    hlist[num_list[i][0]-1]+=1
    wlist[num_list[i][1]-1]+=1

hmax_i=[i for i, v in enumerate(hlist) if v == max(hlist)]
wmax_i=[i for i, v in enumerate(wlist) if v == max(wlist)]
flag=0
for i in hmax_i:
    if flag==0:
        for j in wmax_i:
            if [i+1,j+1] in num_list:
                True
            else:
                flag=1
                break
    else:
        break
if flag==1:
    print(max(hlist)+max(wlist))
else:
    print(max(hlist)+max(wlist)-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())
mx=[[0,i] for i in range(W)]
my=[[0,i] for i in range(H)]
bs =[]
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1][0] += 1
    my[y-1][0] += 1
    bs.append((x-1,y-1))

mx.sort(reverse=True)
my.sort(reverse=True)

ans = 0
mxx = 0
myy = 0
for x in mx:
    mxx = max(mxx, x[0])
    if x[0] + 1 < mxx:
        break
    for y in my:
        myy = max(myy, y[0])
        if y[0] + 1 < myy:
            break
        s = x[0] + y[0]
        if (x[1],y[1]) in bs:
            s -= 1
        ans = max(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = [0] * height
    count_by_width = [0] * width
    bomb_is = [[False] * width for _ in range(height)]
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is[bom_h][bom_w] = True
        # 最大らしき十字はわかるが，交差点にあるかどうかが不明だ。
        # 最大になりそうな十字がいっぱい（前マスに爆弾，など）だと，
        # 結局 O(H*W) で間に合わなそう。3秒あるけど 10^10 じゃあなあ。
        # DP ぽくはあるが，どう DP を作るかだ。

    # h, w にでいくつ爆破できるか。
    # dp = [[0] * width for _ in range(height)]
    # dp[0][0] = count_by_height[0] + count_by_width[0] - bomb_is[0][0]
    ans = 0
    for x in range(height):
        for y in range(width):
            now = count_by_height[x] + count_by_width[y] - bomb_is[x][y]
            ans = max(ans, now)
            # if x < height - 1:
            #     dp[x + 1][y] = (
            #         now + count_by_height[x + 1] - count_by_height[x])
            # if y < width - 1:
            #     dp[x][y + 1] = (
            #         now + count_by_width[y + 1] - count_by_width[y])
    # print(dp)
    return ans


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

Submission status: Time Limit Exceeded

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

def segfunc(x,y):
  return max(x,y)

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)
INF = float("inf")
H,W,M = map(int,input().split())
A = [0 for _ in range(H)]
B = [0 for _ in range(W)]
Treeh = SegmentTree(A,segfunc,-INF)
Treew = SegmentTree(B,segfunc,-INF)
G = [[False]*W for _ in range(H)]
for i in range(M):
  h,w = map(int,input().split())
  h-=1;w-=1
  G[h][w] = True
  Treeh.add(h,1)
  Treew.add(w,1)
X = Treeh.sum(0,H)
Y = Treew.sum(0,W)
MaxX_L = []
for i in range(H):
  #print(Treeh.__getitem__(i))
  if Treeh.__getitem__(i) == X:
    MaxX_L.append(i)
MaxY_L = []
for i in range(W):
  #print(Treeh.__getitem__(i))
  if Treew.__getitem__(i) == Y:
    MaxY_L.append(i)
ans = X+Y
for x in MaxX_L:
  for y in MaxY_L:
    if not G[x][y]:
      print(ans)
      exit()
ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

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

hw = [tuple(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]

hw = set(hw)
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 collections as c

h,w,m = map(int,input().split())
x = []
y = []
z = []
for i in range(m):
    s,t = map(int,input().split())
    x.append(s)
    y.append(t)
    z.append(tuple([s,t]))
a = c.Counter(x)
b = c.Counter(y)
a = a.most_common()
b = b.most_common()
c = []
d = []
e = a[0][1]
f = b[0][1]

for sa in a:
    if sa[1] == e:
        c.append(sa[0])
    else:
        break
for sb in b:
    if sb[1] == f:
        d.append(sb[0])
    else:
        break

fl = 0
ans = e+f-1
for s in c:
    for t in d:
        if tuple([s,t]) not in z:
            fl = 1
            ans += 1
            break
    if fl == 1:
        break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
 
    H, W, M_ko = map(int, input().split())
 
    zahyou = [[0 for i in range(W)] for j in range(H)]
    zahyou_H = [0 for i in range(H)]
    zahyou_W = [0 for i in range(W)]
    
 
    for i in range(M_ko):
        height, width = map(int, input().split())
 
        zahyou[height - 1][width - 1] = 1
        
        zahyou_H[height - 1] += 1
        zahyou_W[width - 1] += 1
 
    CTR_H = collections.Counter(zahyou_H)
    CTR_W = collections.Counter(zahyou_W)
 
    max_h = max(zahyou_H)
    max_w = max(zahyou_W)
 
    len_h = CTR_H[max_h]
    len_w = CTR_W[max_w]
 
    index_h = [i for i, x in enumerate(zahyou_H) if x == max_h]
    index_w = [i for i, x in enumerate(zahyou_W) if x == max_w]
 
 
    maxi = max_h + max_w
    FLAG = False
 
 
    if (len_h == 1 and len_w == 1):    
        maxi -= zahyou[index_h[0]][index_w[0]]
 
 
    else:
        for i in range(len_h):        
            for j in range(len_w):
                val = zahyou[index_h[i]][index_w[j]]
                
                if (val == 0):
                    FLAG = True
                    break
        
        if (not FLAG):
            maxi -= 1
 
    print(maxi)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]
hlist = [0]*h
wlist = [0]*w
for i in hw:
    hlist[i[0]-1]+=1
    wlist[i[1]-1]+=1

h_index = [n for n, v in enumerate(hlist) if v == max(hlist)]

w_index = [n for n, v in enumerate(wlist) if v == max(wlist)]

li = []
for i in h_index:
    for j in w_index:
        li += [hlist[i]+wlist[j]-int([i+1,j+1] in hw)]
print(max(li))

Submission status: Time Limit Exceeded

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

lows = [[0 for j in range(w)] for i in range(h)]
columns = [[0 for j in range(h)] for i in range(w)]
for l in target:
	lows[l[0] - 1][l[1] - 1] = 1
	columns[l[1] - 1][l[0] - 1] = 1

ans = 0
for i in range(h):
	for j in range(w):
		cnt = lows[i].count(1) + columns[j].count(1)
		if lows[i][j] == 1:
			cnt -= 1
		ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h = [0 for i in range(H)]
w = [0 for i in range(W)]
dp = [[0 for i in range(W)] for j in range(H)]

for i in range(M):
    hh, ww = map(int, input().split())
    w[ww - 1] += 1
    dp[hh - 1][ww - 1] += 1

for i in range(H):
    h[i] = sum(dp[i])

hhh = max(h)
www = max(w)
hhhh = [i for i, x in enumerate(h) if x == hhh]
wwww = [i for i, x in enumerate(w) if x == www]
check = 0


for i in hhhh:
    for j in wwww:
        if dp[i][j] == 0:
            check = 1
            break
print(hhh + www - (1 - check))