Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

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

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

1 \leq h_i \leq H

1 \leq w_i \leq W

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

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

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

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

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

Sample Output 3

6



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


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    ans = 0
    for y, x in bombs:
        ans = max(ans, cnt_row[y]+cnt_col[x]-1)
    col_indexs = [i for i in range(w+1)]
    col_indexs.sort(key=lambda x: cnt_col[x])
    cnt_col.sort()
    row_indexs = [i for i in range(h+1)]
    row_indexs.sort(key=lambda x: cnt_row[x])
    cnt_row.sort()
    for i, row_val in zip(reversed(row_indexs), reversed(cnt_row)):
        p = ans - row_val
        idx = bisect_left(cnt_col, p)
        for k in reversed(range(idx, w+1)):
            j = col_indexs[k]
            if (i, j) in bombs:
                continue
            if ans < row_val + cnt_col[k]:
                ans = row_val + cnt_col[k]
                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    ans = 0
    for y, x in bombs:
        ans = max(ans, cnt_row[y]+cnt_col[x]-1)
    col_indexs = [i for i in range(w+1)]
    col_indexs.sort(key=lambda x: cnt_col[x])
    cnt_col.sort()
    for i, row_val in enumerate(cnt_row):
        p = ans - row_val
        idx = bisect_left(cnt_col, p)
        for k in reversed(range(idx, w+1)):
            j = col_indexs[k]
            if (i, j) in bombs:
                continue
            if ans < row_val + cnt_col[k]:
                ans = row_val + cnt_col[k]
                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    ans = 0
    for y, x in bombs:
        ans = max(ans, cnt_row[y]+cnt_col[x]-1)
    col_indexs = [i for i in range(w+1)]
    col_indexs.sort(key=lambda x: cnt_col[x])
    cnt_col.sort()
    for i, row_val in enumerate(cnt_row):
        p = ans - row_val
        idx = bisect_left(cnt_col, p)
        for k in range(idx, w+1):
            j = col_indexs[k]
            if (i, j) in bombs:
                continue
            if ans < row_val + cnt_col[k]:
                ans = row_val + cnt_col[k]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
########### E
H, W, M = map(int, input().split())
bombs = []
for _ in range(M):
    bomb = list(map(int, input().split()))
    bombs.append(bomb)
 
H_list = [0]*H
W_list = [0]*W
sign = True
for i in range(M):
    H_list[bombs[i][0]-1] += 1
    W_list[bombs[i][1]-1] += 1
 
max_H = [i for i,k in enumerate(H_list) if k == max(H_list)]
max_W = [i for i,k in enumerate(W_list) if k == max(W_list)]
 
cross = []
 
for i in max_H:
    for k in max_W:
        if [i+1,k+1] not in bombs:
            sign = False
            print(max(H_list) + max(W_list))
            break
    break
 
if sign:
    print(max(H_list) + max(W_list) -1)

Submission status: Time Limit Exceeded

Solution code:
########### E
H, W, M = map(int, input().split())
bombs = []
for _ in range(M):
    bomb = list(map(int, input().split()))
    bombs.append(bomb)

H_list = [0]*H
W_list = [0]*W
sign = True
for i in range(M):
    H_list[bombs[i][0]-1] += 1
    W_list[bombs[i][1]-1] += 1

max_H = [i for i,k in enumerate(H_list) if k == max(H_list)]
max_W = [i for i,k in enumerate(W_list) if k == max(W_list)]

cross = []

for i in max_H:
    for k in max_W:
        if [i+1,k+1] not in bombs:
            sign = False
            print(max(H_list) + max(W_list))
            break
    break

if sign:
    print(max(H_list) + max(W_list) -1)

Submission status: Time Limit Exceeded

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

H, W, M = nn()
T = nm(M)

for i in range(M):
    T[i] = ldec(T[i])

dh = array1(H)
dw = array1(W)

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

dhlist = []
dwlist = []

ansh = max(dh)
for i in range(len(dh)):
    if dh[i] == ansh:
        dhlist.append(i)

answ = max(dw)
for i in range(len(dw)):
    if dw[i] == answ:
        dwlist.append(i)

ans = ansh + answ

for i in dhlist:
    for j in dwlist:
        if [i, j] not in T:
            print(ans)
            exit(0)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=[]
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.append([th,tw])

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

for i in h_cand:
  for j in w_cand:
    if [i,j] not in l:
      print(h_max+w_max)
      exit()

print(h_max+w_max-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

H, W, M = nn()
T = nm(M)

for i in range(M):
    T[i] = ldec(T[i])

dh = array2(H, 0)
dw = array2(W, 0)

for i in range(M):
    dh[T[i][0]].append(T[i])
    dw[T[i][1]].append(T[i])

def lenmax(A):
    m = 0
    for i in range(len(A)):
        if m < len(A[i]):
            m = len(A[i])

    ret = []
    for i in range(len(A)):
        if len(A[i]) == m:
            #print(m, A[i])
            ret.append(A[i])

    return m, ret

x, dhlist = lenmax(dh)
y, dwlist = lenmax(dw)
ans = x + y

def judge(a, L):
    for i in range(len(L)):
        for j in range(len(L[i])):
            if a == L[i][j]:
                return True
    return False

for i in range(len(dhlist)):
    for j in range(len(dwlist)):
        if [dhlist[i][0][0], dwlist[j][0][1]] not in T:
            print(ans)
            exit(0)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bombs = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(M)]
field = [[False] * W for _ in range(H)]

max_hw = max(H, W)
H_count = {i:0 for i in range(max_hw)}
W_count = {i:0 for i in range(max_hw)}

for i in range(M):
    h, w = bombs[i]
    field[h][w] = True
    H_count[h] += 1
    W_count[w] += 1


A = max(H_count.values())
B = max(W_count.values())
Ah = []
Bw = []

for i in range(max_hw):
    if H_count[i] == A:
        Ah.append(i)
    if W_count[i] == B:
        Bw.append(i)

ans = A + B
FLG = True
for h in Ah:
    for w in Bw:
        if not field[h][w]:
            FLG = False
            break
    if not FLG:
        break

print(ans - FLG)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = [int(x) for x in input().split()]

bomb = []
row = [0] * (H + 1)
column = [0] * (W + 1)
h_max = []
w_max = []

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

A = max(row)
B = max(column)

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

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

overlap = 0
for i in range(M):
    h = bomb[i][0]
    w = bomb[i][1]
    if (h in h_max) & (w in w_max):
        overlap += 1

cand = len(h_max) * len(w_max)

if cand > overlap:
    print(A + B)
else:
    print(A + B - 1)

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)
count=0

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 range(M):
        if T[i][0] in h_max and T[i][1] in w_max:
            count+=1
    if count==len(h_max)*len(w_max):
        print(int(h+w)-1)
    else:
        print(int(h+w))
    
else:
    print(int(h+w))

Submission status: Time Limit Exceeded

Solution code:
def calc():
  H,W,M = map(int, input().split())
  s = []
  hcount = [0]*H
  wcount = [0]*W
  for m in range(M):
    h,w = map(int, input().split())
    h = h - 1
    w = w - 1
    hcount[h] = hcount[h] + 1
    wcount[w] = wcount[w] + 1
    s.append([h,w])
  hmax = max(hcount)
  wmax = max(wcount)
  for h in range(H):
    for w in range(W):
      if hcount[h] != hmax or wcount[w] != wmax or [h,w] in s:
        continue
      else:
        return hmax + wmax
  return hmax + wmax - 1

if __name__ == '__main__':
    print(calc())

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bombs = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(M)]

max_hw = max(H, W)
H_count = {i:0 for i in range(max_hw)}
W_count = {i:0 for i in range(max_hw)}

for i in range(M):
    h, w = bombs[i]
    H_count[h] += 1
    W_count[w] += 1


A = max(H_count.values())
B = max(W_count.values())
Ah = []
Bw = []

for i in range(max_hw):
    h, count_h = i, H_count[i]
    w, count_w = i, W_count[i]

    if count_h == A:
        Ah.append(h)
    if count_w == B:
        Bw.append(w)

ans = A + B
FLG = True
for h in Ah:
    for w in Bw:
        if [h, w] not in bombs:
            FLG = False
            break
    if not FLG:
        break

print(ans - FLG)

Submission status: Time Limit Exceeded

Solution code:
def calc():
  H,W,M = map(int, input().split())
  s = []
  hcount = [0]*H
  wcount = [0]*W
  for m in range(M):
    h,w = map(int, input().split())
    h = h - 1
    w = w - 1
    hcount[h] = hcount[h] + 1
    wcount[w] = wcount[w] + 1
    s.append([h,w])
  hmax = max(hcount)
  wmax = max(wcount)
  hmode = []
  wmode = []
  for h in range(H):
    if hcount[h] == hmax:
      hmode.append(h)
  for w in range(W):
    if wcount[w] == wmax:
      wmode.append(w)
  for h in hmode:
    for w in wmode:
      if ([h,w] in s):
        continue
      return hmax + wmax
  return hmax + wmax - 1

if __name__ == '__main__':
    print(calc())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

h,w,m = readints()

r = [0]*h
c = [0]*w

d = [set() for i in range(h)]
for i in range(m):
    a,b = (x-1 for x in readints())
    r[a] += 1
    c[b] += 1
    d[a].add(b)

R = [i for i,x in enumerate(r) if x==max(r)]
C = [i for i,x in enumerate(c) if x==max(c)]

flag = 1
if len(R)*len(C)>m:
    flag = 0
else:
    for x in R:
        for y in C:
            if y not in d[x]:
                flag = 0
                break

print(max(r)+max(c)-flag)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(M)]

rows, columns = [0]*H, [0]*W
for h, w in hw:
    rows[h-1] += 1
    columns[w-1] += 1
max_r, max_c = max(rows), max(columns)

argmax_r, argmax_c = [], []
for i in range(H):
    if max_r == rows[i]:
        argmax_r.append(i)
for i in range(W):
    if max_c == columns[i]:
        argmax_c.append(i)

for r in argmax_r:
    for c in argmax_c:
        if [r+1,c+1] not in hw:
            print(max_r + max_c)
            exit()

print(max_r + max_c - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import statistics
H,W,M = map(int, input().split())
S = np.array([list([int(s) for s in input().split()]) for i in range(M)]) - 1
Hlist = S[:,0]
Wlist = S[:,1]
Hunique,Hcount = np.unique(Hlist, return_counts=True)
Wunique,Wcount = np.unique(Wlist, return_counts=True)
Hmode = np.array(list(Hunique[Hcount == max(Hcount)]))
Wmode = np.array(list(Wunique[Wcount == max(Wcount)]))
judge = -1
slist = []
for m in range(M):
  slist.append(list(S[m,:]))
for h in Hmode:
  for w in Wmode:
    if ([h,w] in slist) == False:
      judge = 0
      break
print(max(Hcount) + max(Wcount) + judge)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import statistics
H,W,M = map(int, input().split())
S = np.array([list([int(s) for s in input().split()]) for i in range(M)]) - 1
Hlist = S[:,0]
Wlist = S[:,1]
Hunique,Hcount = np.unique(Hlist, return_counts=True)
Wunique,Wcount = np.unique(Wlist, return_counts=True)
Hmode = np.array(list(Hunique[Hcount == max(Hcount)]))
Wmode = np.array(list(Wunique[Wcount == max(Wcount)]))
judge = -1
for h in Hmode:
  for w in Wmode:
    c = True
    for m in range(M):
      if (S[m,0] == h and S[m,1] == w):
        c = False
    if c:
      judge = 0
print(max(Hcount) + max(Wcount) + judge)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import defaultdict
dic1 = defaultdict(int)

def even(n): return 1 if n%2==0 else 0


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

columns = [0]*W
row = [0]*H
for i in range(M):
    h,w = map(int,readline().split())
    h,w = h-1,w-1
    dic1[(h,w)] = 1
    columns[w] += 1
    row[h] += 1

def rank(lst,syoujun=False):
    res2 = list(set(lst))
    ans = []
    if syoujun:
        res2.sort()
    else:
        res2.sort(reverse=True)
    dic1 = dict()
    for i in range(len(res2)):
        dic1[res2[i]] = i
    for idx,i in enumerate(lst):
        if dic1[i] == 0:
            ans.append(idx)
    
    return ans

col2 = rank(columns)
row2 = rank(row)

ans = 0
for i in col2:
    for j in row2:
        if dic1[(j,i)]:
            ans = max(ans,columns[i]+row[j]-1)
        else:
            ans = max(ans,columns[i]+row[j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
flag = 0
for hh in h_dict:
    if h_dict[hh] < h_max_count:
        continue
    for ww in w_dict:
        if w_dict[ww] < w_max_count:
            continue
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split(" ")) 
hl=[] 
wl=[] 
c=[list(input().split(" "))for i in range(M)]
for i in range(M): 
    hl.append(c[i][0]) 
    wl.append(c[i][1]) 
from collections import Counter 
ac=Counter(hl)
bc=Counter(wl)

a=ac.most_common()
b=bc.most_common()
count=a[0][1]+b[0][1]-1
def f(d):
    #print(d)
    for i in range(len(d)):
        if d[0][1]>d[i][1]:
            return int(i)
    else:
       
        return len(d)

    
for i in range(f(a)):
    for j in range(f(b)):
        if [a[i][0],b[j][0]] not in c:
            count+=1
            break
    else:
        continue
    break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H,W,M=map(int,input().split())
l=[]
nh=[0]*H
nw=[0]*W
for _ in range(M):
    h,w=map(int,input().split())
    h-=1
    w-=1
    l.append((h,w))
    nh[h]+=1
    nw[w]+=1
hmax=max(nh)
wmax=max(nw)
is_h=[i for i in range(H) if nh[i]==hmax]
is_w=[i for i in range(W) if nw[i]==wmax]

for i_h,i_w in itertools.product(is_h,is_w):
    if not ((i_h,i_w) in l):
        print(hmax+wmax)
        break
else:
    print(hmax+wmax-1)

Submission status: Time Limit Exceeded

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

max_h, max_w = max(cnt_h), max(cnt_w)

h_list = [h for h in range(H) if cnt_h[h] == max_h]
w_list = [w for w in range(W) if cnt_w[w] == max_w]

from itertools import product

for h, w in product(h_list, w_list):
    if (h, w) not in set(hw):
        print(max_h + max_w)
        break
else:
    print(max_h + max_w - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

height, width, num = map(int, input().split())

bomb_rows = np.zeros(height)
bomb_cols = np.zeros(width)
bomb_pos = []
for index in range(num):
  x, y = map(int, input().split())
  bomb_rows[x - 1] += 1
  bomb_cols[y - 1] += 1
  bomb_pos.append([x - 1, y - 1])
  
max_row = 0
max_row_pos = []
max_col = 0
max_col_pos = []

for index in range(height):
  if bomb_rows[index] > max_row:
    max_row = bomb_rows[index]
    max_row_pos = [index]
  elif bomb_rows[index] == max_row:
    max_row_pos.append(index)
    
for index in range(width):
  if bomb_cols[index] > max_col:
    max_col = bomb_cols[index]
    max_col_pos = [index]
  elif bomb_cols[index] == max_col:
    max_col_pos.append(index)

if len(max_row_pos) * len(max_col_pos) > num:
  max_value = int(max_row + max_col)
else:
  all_pos_num = len(max_row_pos) * len(max_col_pos)
  for item in bomb_pos:
    
    for pos_row in max_row_pos:
      if item[0] == pos_row:
        for pos_col in max_col_pos:
          if item[1] == pos_col:
            all_pos_num -= 1
            break
    '''  
    if item[0] in max_row_pos and item[1] in max_col_pos:
      all_pos_num -= 1
    '''
    if all_pos_num == 0:
      break
  if all_pos_num == 0:
    max_value = int(max_row + max_col - 1)
  else:
    max_value = int(max_row + max_col)

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

height, width, num = map(int, input().split())

bomb_rows = np.zeros(height)
bomb_cols = np.zeros(width)
bomb_pos = []
for index in range(num):
  x, y = map(int, input().split())
  bomb_rows[x - 1] += 1
  bomb_cols[y - 1] += 1
  bomb_pos.append([x - 1, y - 1])
  
max_row = 0
max_row_pos = []
max_col = 0
max_col_pos = []

for index in range(height):
  if bomb_rows[index] > max_row:
    max_row = bomb_rows[index]
    max_row_pos = [index]
  elif bomb_rows[index] == max_row:
    max_row_pos.append(index)
    
for index in range(width):
  if bomb_cols[index] > max_col:
    max_col = bomb_cols[index]
    max_col_pos = [index]
  elif bomb_cols[index] == max_col:
    max_col_pos.append(index)

if len(max_row_pos) * len(max_col_pos) > num:
  max_value = int(max_row + max_col)
else:
  all_pos_num = len(max_row_pos) * len(max_col_pos)
  for item in bomb_pos:
    if item[0] in max_row_pos and item[1] in max_col_pos:
      all_pos_num -= 1
    if all_pos_num == 0:
      break
  if all_pos_num == 0:
    max_value = int(max_row + max_col - 1)
  else:
    max_value = int(max_row + max_col)

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

height, width, num = map(int, input().split())

bomb_rows = np.zeros(height)
bomb_cols = np.zeros(width)
bomb_pos = []
for index in range(num):
  x, y = map(int, input().split())
  bomb_rows[x - 1] += 1
  bomb_cols[y - 1] += 1
  bomb_pos.append([x - 1, y - 1])
  
max_row = 0
max_row_pos = []
max_col = 0
max_col_pos = []

for index in range(height):
  if bomb_rows[index] > max_row:
    max_row = bomb_rows[index]
    max_row_pos = [index]
  elif bomb_rows[index] == max_row:
    max_row_pos.append(index)
    
for index in range(width):
  if bomb_cols[index] > max_col:
    max_col = bomb_cols[index]
    max_col_pos = [index]
  elif bomb_cols[index] == max_col:
    max_col_pos.append(index)

if len(max_row_pos) * len(max_col_pos) > num:
  max_value = int(max_row + max_col)
else:
  flag = True
  for index in range(len(max_row_pos)):
    if flag:
      for jndex in range(len(max_col_pos)):
        if not [max_row_pos[index], max_col_pos[jndex]] in bomb_pos:
          max_value = int(max_row + max_col)
          flag = False
  if flag:
  	max_value = int(max_row + max_col - 1)

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
h_cnt = [0 for _ in range(h)]
w_cnt = [0 for _ in range(w)]
mat = [[0 for _ in range(w)] for _ in range(h)]
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    h_cnt[y] += 1
    w_cnt[x] += 1
    mat[y][x] += 1
h_dict = {i:v for i, v in enumerate(h_cnt)}
w_dict = {i:v for i, v in enumerate(w_cnt)}
h_max = max(h_dict.values())
w_max = max(w_dict.values())
h_max_induce = [i for i in h_dict.keys() if h_dict[i] == h_max]
w_max_induce = [i for i in w_dict.keys() if w_dict[i] == w_max]

for h_idx in h_max_induce:
    for w_idx in w_max_induce:
        if mat[h_idx][w_idx] == 0:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

h,w,m=nii()

h_bomb=[0 for i in range(h)]
w_bomb=[0 for i in range(w)]

l=[]
for i in range(m):
  th,tw=nii()
  th-=1
  tw-=1
  h_bomb[th]+=1
  w_bomb[tw]+=1
  l.append([th,tw])

h_max=max(h_bomb)
w_max=max(w_bomb)

h_cand=[]
w_cand=[]

for i in range(len(h_bomb)):
  if h_bomb[i]==h_max:
    h_cand.append(i)

for i in range(len(w_bomb)):
  if w_bomb[i]==w_max:
    w_cand.append(i)

ans=0
for i in h_cand:
  for j in w_cand:
    if [i,j] in l:
      ans=max(ans,h_max+w_max-1)
    else:
      ans=max(ans,h_max+w_max)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
h_l = [0]
w_l = [0]
count_h =[0]
count_w = [0]
for i in range(1, M+1):
    h, w = map(int, input().split())
    h_l.append(h)
    w_l.append(w)

for h in range(1, H+1):
    count = 0
    for i in range(1, M+1):
        if h == h_l[i]:
            count += 1
        else:
            pass
    count_h.append(count)

for w in range(1, W+1):
    count = 0
    for i in range(1, M+1):
        if w == w_l[i]:
            count += 1
        else:
            pass
    count_w.append(count)
        
max_h = max(count_h)
max_w = max(count_w)

def get_index(num, lis):
    ind_l = []
    lis = list(map(str, lis))
    while str(num) in lis:
        ind = lis.index(str(num))
        ind_l.append(ind)
        lis.pop(ind)
        lis.insert(ind,"a")
    return ind_l

ind_h = get_index(max_h, count_h)
ind_w = get_index(max_w, count_w)
ans_nml = max_h + max_w
ans_mlt = max_h + max_w -1
ans = 0
for h in ind_h:
    for w in ind_w:
        check = 0
        for i in range(1, M+1):
            if h == h_l[i] and w == w_l[i]:
                check = 1
            else:
                pass
        if check == 1:
            ans = max(ans, max_h + max_w -1)
        else:
            ans = max_h + max_w

print("{0}".format(ans))

Submission status: Time Limit Exceeded

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

h_dict = [0]+[set() for i in range(H)]
w_dict = [0]+[set() for i in range(W)] 
target_set = set()
for i in range(M):
    h,w = map(int, input().split())
    h_dict[h].add(w)
    w_dict[w].add(h)
    target_set.add((h,w))
   
h_len_list = [0]+[len(h_dict[i]) for i in range(1,H+1)]
w_len_list = [0]+[len(w_dict[i]) for i in range(1,W+1)]

maxlen_h_value = max(h_len_list)
maxlen_w_value = max(w_len_list)
h_max_index = {i for i, x in enumerate(h_len_list) if x == max(h_len_list)}
w_max_index = {i for i, x in enumerate(w_len_list) if x == max(w_len_list)}

bomb_set = set()
for h in h_max_index:
    for w in w_max_index:
        bomb_set.add((h,w))
        
bomb_set -= target_set

if len(bomb_set) == 0:
    print(maxlen_h_value + maxlen_w_value - 1)
else:
    print(maxlen_h_value + maxlen_w_value)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

ans = max(h) + max(w)
index_num_h = [n for n, v in enumerate(h) if v == max(h)]
index_num_w = [n for n, v in enumerate(w) if v == max(w)]

cnt = 0
for item in item_list:
    if item[0] in index_num_h and item[1] in index_num_w:
        cnt += 1

x = len(index_num_h) * len(index_num_w)
if cnt == x:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

ans = max(h) + max(w)
index_num_h = [n for n, v in enumerate(h) if v == max(h)]
index_num_w = [n for n, v in enumerate(w) if v == max(w)]

cnt = -1
for h_i in index_num_h:
    for w_i in index_num_w:
        d = [h_i, w_i]
        if d not in item_list:
            cnt = 0
            break

if cnt == -1:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

H, W, M = map(int, input().split())
h = [-1 for _ in range(M)]
w = [-1 for _ in range(M)]
s = []
for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    s.append([h[i], w[i]])

# calc
hs = [0 for _ in range(H)]
ws = [0 for _ in range(W)]
for i in range(M):
    hs[h[i]] += 1
    ws[w[i]] += 1

#print('hs =', hs)
#print('ws =', ws)

hmax = max(hs)
wmax = max(ws)

ks = []
js = []

# 最大値の荷物がある場所を覚えておく
for k in range(H):
    if hmax == hs[k]:
        ks.append(k)
for j in range(W):
    if wmax == ws[j]:
        js.append(j)

ans = hmax + wmax

# クロスする場所に荷物があるかないかの確認
for k in range(len(ks)):
    for j in range(len(js)):
        if [ks[k], js[j]] not in s:
            print(ans)
            exit()
print(ans-1)