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_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 = 0
for h in ind_h:
    for w in ind_w:
        ans_l = []
        for i in range(1, M+1):
            if h == h_l[i] and w == w_l[i]:
                ans_l.append(max_h + max_w -1)
            else:
                ans_l.append(max_h + max_w)
        ans = max(ans, min(ans_l))

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w, m = map(int, input().split())    
    h_w = set()
    for i in range(m):
        h_w.add(tuple(map(int, input().split())))

    x = [0]*h
    y = [0]*w

    for p in h_w:
        x[p[0]-1] += 1
        y[p[1]-1] += 1
    
    idx_x = [i for i, v in enumerate(x) if v == max(x)]
    idx_y = [i for i, v in enumerate(y) if v == max(y)]

    
    for i in idx_x:
        for j in idx_y:
            if not((i+1, j+1) in set(h_w)):
                print(max(x) + max(y))
                return 0

    print(max(x) + max(y) - 1)    
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1

for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
    else:
        continue
    break

ans = mxx + myy - a
print(ans)

Submission status: Time Limit Exceeded

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

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

    bomb_set = set()
    # 配列で要素を作ると要素数が$10^8$超える場合、setで要素の座標を持っておく


    for i,j in targets:
        col[i] += 1
        row[j] += 1
        bomb_set.add((i,j))

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

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

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

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
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 = set([i for i, x in enumerate(h_len_list) if x == max(h_len_list)])
w_max_index = set([i for i, x in enumerate(w_len_list) if x == max(w_len_list)])

if len(h_max_index)*len(w_max_index) > M:
    print(maxlen_h_value + maxlen_w_value)
else:
    for h in h_max_index:
        for w in w_max_index:
            if (h,w) not in target_set:
                print(maxlen_h_value + maxlen_w_value)
                exit()
    print(maxlen_h_value + maxlen_w_value - 1)

Submission status: Time Limit Exceeded

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

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1
for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
ans = mxx + myy - a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: continue
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
# タプルは更新と削除は不可だからそれらの操作をしない時はリストよりタプルを使うべし
hw = []
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.append((h, w))
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def solve(strings_max, rows_max, mapa):
        summa = maxs + maxr - 1
        if summa == h + w - 1 or summa == m:
            return summa
        for h_item in strings_max:
            for w_item in rows_max:
                if w_item not in mapa.get(h_item, []):
                    return summa + 1
        return summa


    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    maxs = max(strings)
    maxr = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == maxs:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == maxr:
            rows_max.append(i)
    
    ans = solve(strings_max, rows_max, mapa)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hw = []
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if [i + 1, j + 1] not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if [i + 1, j + 1] not in hw:
            print(max_h + max_w)
            exit()

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def solve(strings_max, rows_max, mapa):
        summa = maxs + maxr - 1
        if summa == h + w - 1:
            return summa
        for h_item in strings_max:
            for w_item in rows_max:
                if w_item not in mapa.get(h_item, []):
                    return summa + 1
        return summa


    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    maxs = max(strings)
    maxr = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == maxs:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == maxr:
            rows_max.append(i)
    
    ans = solve(strings_max, rows_max, mapa)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

new_H = [h for h in range(H) if A[h + 1] == max_A]
new_W = [w for w in range(W) if B[w + 1] == max_B]

max_num = max_A + max_B - 1
for i in new_H:
    for j in new_W:
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] not in hw:
                print(max_A + max_B)
                exit()

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

new_H = []
for i, v in A.items():
    if v == max_A:
        new_H.append(i - 1)

new_W = []
for i, v in B.items():
    if v == max_B:
        new_W.append(i - 1)

new_H.sort()
new_W.sort()
max_num = max_A + max_B - 1
for i in new_H:
    for j in new_W:
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] in hw:
                continue
            else:
                print(max_A + max_B)
                exit()

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

new_H = []
for i, v in A.items():
    if v == max_A:
        new_H.append(i - 1)

new_W = []
for i, v in B.items():
    if v == max_B:
        new_W.append(i - 1)

new_H.sort()
new_W.sort()
max_num = 0
for i in new_H:
    for j in new_W:
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] in hw:
                max_num = max(max_num, max_A + max_B - 1)
            else:
                max_num = max(max_num, max_A + max_B)

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

max_num = 0
for i in range(H):
    for j in range(W):
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] in hw:
                max_num = max(max_num, max_A + max_B - 1)
            else:
                max_num = max(max_num, max_A + max_B)

print(max_num)

Submission status: Time Limit Exceeded

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

xy = [list(map(int, input().split())) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

x_score = [0]*(H+1)
y_score = [0]*(W+1)
total = 0

for i in range(M):
	x_score[x[i]] += 1
	y_score[y[i]] += 1



total = max(x_score) +  max(y_score)


xx = [i for i, v in enumerate(x_score) if v == max(x_score)]
yy = [i for i, v in enumerate(y_score) if v == max(y_score)]

new = []
for a in xx:
	for b in yy:
		new.append([a,b])


cue = 1
for x in new:
	if x not in xy:
		cue = 0

total -= cue

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict, Counter
hs=[]
ws=[]
hd2=defaultdict(list)
wd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hs.append(h0)
    hd2[h0].append(w0)
    ws.append(w0)
    wd2[w0].append(h0)

hd=Counter(hs)
wd=Counter(ws)
hmax=max(hd.values())
wmax=max(wd.values())
max_h_list = [kv[0] for kv in hd.items() if kv[1] == hmax]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == wmax]

ans=float('inf')

if len(max_h_list)>=len(max_w_list):
    for x in max_h_list:
        hlist=hd2[x]
        for y in max_w_list:
            if y in hlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
else:
    for x in max_w_list:
        wlist=wd2[x]
        for y in max_h_list:
            if y in wlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
print(hmax+wmax-ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [list(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h = max(num_in_h.values())
max_w = max(num_in_w.values())
max_h_list = [kv for kv in num_in_h.items() if kv[1] == max_h]
max_w_list = [kv for kv in num_in_w.items() if kv[1] == max_w]
ans = max_h + max_w

#print([max_h[0], max_w[0]] in targets)
flag = False
for h in max_h_list:
    for w in max_w_list:
        if [h[0], w[0]] not in targets:
            flag = True
            break

print(ans if flag == True else ans-1)

Submission status: Time Limit Exceeded

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

bomb = [[False for i in range(w)] for j in range(h)]
cnth = [0 for i in range(h)]
cntw = [0 for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  cnth[x] += 1
  cntw[y] += 1
  bomb[x][y] = True
maxh = max(cnth)
maxw = max(cntw)

xx = []
yy = []
for i in range(h):
  if maxh == cnth[i]:
    xx.append(i)
for i in range(w):
  if maxw == cntw[i]:
    yy.append(i)


ans = maxh + maxw -1
for i in xx:
  for j in yy:
    if not bomb[i][j]:
      ans += 1
      print (ans)
      exit()
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h_set = set([i for i, v in enumerate(num_in_h) if v == max(num_in_h)])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max(num_in_w)])
ans = max(num_in_h) + max(num_in_w) -1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = []
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.append((t_h, t_w))
targets = set(targets)

max_h_set = set([i for i, v in enumerate(num_in_h) if v == max(num_in_h)])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max(num_in_w)])
ans = max(num_in_h) + max(num_in_w) -1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)

Submission status: Time Limit Exceeded

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

bomb = [[False for i in range(w)] for j in range(h)]
cnth = [0 for i in range(h)]
cntw = [0 for i in range(w)]
for i in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  cnth[x] += 1
  cntw[y] += 1
  bomb[x][y] = True

ans = 0
tmp = 0
for i in range(h):
  for j in range(w):
    tmp = cnth[i]+cntw[j]
    if bomb[i][j]:
      tmp -= 1
    ans = max(ans, tmp)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = []
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.append((t_h, t_w))

max_h_set = set([i for i, v in enumerate(num_in_h) if v == max(num_in_h)])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max(num_in_w)])
ans = max(num_in_h) + max(num_in_w)

point = 0
comb = len(max_h_set) * len(max_w_set)
targets = set(targets)
for t in targets:
    if t[0] in max_h_set and t[1] in max_w_set:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [tuple(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_set = set(kv[0] for kv in num_in_h.items() if kv[1] == max(num_in_h.values()))
max_w_set = set(kv[0] for kv in num_in_w.items() if kv[1] == max(num_in_w.values()))
ans = max(num_in_h.values()) + max(num_in_w.values())

point = 0
comb = len(max_h_set) * len(max_w_set)
targets = set(targets)
for t in targets:
    if t[0] in max_h_set and t[1] in max_w_set:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [tuple(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_list = [kv[0] for kv in num_in_h.items() if kv[1] == max(num_in_h.values())]
max_w_list = [kv[0] for kv in num_in_w.items() if kv[1] == max(num_in_w.values())]
ans = max(num_in_h.values()) + max(num_in_w.values())

point = 0
comb = len(max_h_list) * len(max_w_list)
targets = set(targets)
for t in targets:
    if t[0] in max_h_list and t[1] in max_w_list:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [list(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_list = [kv[0] for kv in num_in_h.items() if kv[1] == max(num_in_h.values())]
max_w_list = [kv[0] for kv in num_in_w.items() if kv[1] == max(num_in_w.values())]
ans = max(num_in_h.values()) + max(num_in_w.values())

#print(max_h_list, max_w_list)
point = 0
comb = len(max_h_list) * len(max_w_list)
for t in targets:
    if t[0] in max_h_list and t[1] in max_w_list:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy
h,w,m = map(int,input().split())
hight = [0]*h
width = [0]*w
matrix =[0]*h
for i in range(h):
    matrix[i] = [0]*w
for i in range(m):
    hi,wi = map(int,input().split())
    hight[hi-1] += 1
    width[wi-1] += 1
    matrix[hi-1][wi-1] += 1
max_vh = max(hight)
max_vw = max(width)
max_h = list()
max_w = list()
for i in range(len(hight)):
    if(hight[i] == max_vh):
        max_h.append(i)
for i in range(len(width)):
    if(width[i] == max_vw):
        max_w.append(i)
# print(max_h,max_w)
if(len(max_h)==0 and len(max_w)):
    print(hight[max_h[0]]+width[max_w[0]]-matrix[max_h[0]][max_w[0]])
elif(len(max_h)!=0 and len(max_w)==0):
    ans = 0
    for i in range(len(max_h)):
        ans = max(ans,hight[max_h[i]]+width[max_w][0]-matrix[max_h[i]][max_w][0])
    print(ans)
elif(len(max_h)==0 and len(max_w)!=0):
    ans = 0
    for i in range(len(max_w)):
        ans = max(ans,hight[max_h[0]]+width[max_w[i]]-matrix[max_h[0]][max_w[i]])
    print(ans)
else:
    ans = 0
    for i in range(len(max_h)):
        for j in range(len(max_w)):
            ans = max(ans,hight[max_h[i]]+width[max_w[j]]-matrix[max_h[i]][max_w[j]])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [list(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_list = [kv for kv in num_in_h.items() if kv[1] == max(num_in_h.values())]
max_w_list = [kv for kv in num_in_w.items() if kv[1] == max(num_in_w.values())]
ans = max(num_in_h.values()) + max(num_in_w.values())

#print([max_h[0], max_w[0]] in targets)
flag = False
for h in max_h_list:
    for w in max_w_list:
        if [h[0], w[0]] not in targets:
            flag = True
            break

print(ans if flag == True else ans-1)

Submission status: Time Limit Exceeded

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

import numpy as np

H,W,M=map(int,input().split())
hs=[0]*H
ws=[0]*W
#A=dict()
A=[]
for i in range(M):
    h,w=map(int,input().split())
    hs[h-1]+=1
    ws[w-1]+=1
    A.append((h-1,w-1))

MH=max(hs)
MW=max(ws)
ans=MH+MW

mh=[]
for i in range(H):
    if hs[i]==MH:
        mh.append(i)
mw=[]
for i in range(W):
    if ws[i]==MW:
        mw.append(i)

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

    if N ==0: ans-=1

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
h=[0]*M
w=[0]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())
t=[0]*H
y=[0]*W
for i in range(H):
    a = 0
    for j in range(M):
        if h[j] == i+1:
            a = a+1
        t[i] = a
for i in range(W):
    a = 0
    for j in range(M):
        if w[j] == i+1:
            a = a+1
        y[i] = a       
maxt = max(t)
maxy = max(y)
lt=[]
ly=[]
for i in range(len(t)):
    if t[i] == maxt:
        lt.append(i+1)
for i in range(len(y)):
    if y[i] == maxy:
        ly.append(i+1)
b = 0
for i in range(M):
    if h[i] in lt and w[i] in ly:
        b = b + 1
if b == len(lt)*len(ly):
    print(maxt+maxy-1)
else:
    print(maxt+maxy)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, deque
H, W, M = map(int, input().split())
h_list = deque()
w_list = deque()
hw = deque()
for i in range(M):
    h, w = map(int, input().split())
    h_list.append(h)
    w_list.append(w)
    hw.append([h, w])
h_col = Counter(h_list)
w_col = Counter(w_list)
h_max_num = h_col.most_common()[0][1]
w_max_num = w_col.most_common()[0][1]
h_max_list = deque([h_col.most_common()[0][0]])
w_max_list = deque([w_col.most_common()[0][0]])

for i in range(1, len(h_col)):
    if h_col.most_common()[i][1] == h_max_num:
        h_max_list.append(h_col.most_common()[i][0])
    else:
        break
for i in range(1, len(w_col)):
    if w_col.most_common()[i][1] == w_max_num:
        w_max_list.append(w_col.most_common()[i][0])
    else:
        break
for i in h_max_list:
    for j in w_max_list:
        if [i, j] not in hw:
            print(h_max_num + w_max_num)
            exit()
print(h_max_num + w_max_num - 1)

Submission status: Time Limit Exceeded

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

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

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

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

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

num = len(r_check) * len(c_check)

ans = row_max + col_max - 1
flg = False
if M < num:
    ans = row_max + col_max
else:
    for r in r_check:
        if flg:
            break
        for c in c_check:
            if not [r, c] in bomb:
                ans = row_max + col_max
                flg = True
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
H, W, M = map(int, input().split())
h_list = []
w_list = []
hw = []
for i in range(M):
    h, w = map(int, input().split())
    h_list.append(h)
    w_list.append(w)
    hw.append([h, w])
h_col = collections.Counter(h_list)
w_col = collections.Counter(w_list)
h_max_num = h_col.most_common()[0][1]
w_max_num = w_col.most_common()[0][1]
h_max_list = [h_col.most_common()[0][0]]
w_max_list = [w_col.most_common()[0][0]]

for i in range(1, len(h_col)):
    if h_col.most_common()[i][1] == h_max_num:
        h_max_list.append(h_col.most_common()[i][0])
    else:
        break
for i in range(1, len(w_col)):
    if w_col.most_common()[i][1] == w_max_num:
        w_max_list.append(w_col.most_common()[i][0])
    else:
        break
for i in h_max_list:
    for j in w_max_list:
        if [i, j] not in hw:
            print(h_max_num + w_max_num)
            exit()
print(h_max_num + w_max_num - 1)

Submission status: Time Limit Exceeded

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

xy = [list(map(int, input().split())) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

x_score = [0]*(H+1)
y_score = [0]*(W+1)
total = 0
def has_duplicates2(seq):
    seen = []
    unique_list = [x for x in seq if x not in seen and not seen.append(x)]
    return len(seq) - len(unique_list)

for i in range(M):
	x_score[x[i]] += 1
	y_score[y[i]] += 1



total = max(x_score) +  max(y_score)

"""
if [x_score.index(max(x_score)), y_score.index(max(y_score))] in xy:
	total -= 1
"""
xx = [i for i, v in enumerate(x_score) if v == max(x_score)]
yy = [i for i, v in enumerate(y_score) if v == max(y_score)]
list_len = len(xx)*len(yy)

for a in xx:
	for b in yy:
		xy.append([a,b])


if has_duplicates2(xy) == list_len:
	total -= 1

print(total)

Submission status: Time Limit Exceeded

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

G = []
for i in range(M):
    x, y = map(int, input().split())
    g = [x, y]
    G.append(g)

h = [0]*H
for i in range(M):
    h[G[i][0]-1] += 1
h_max = max(h)
h_mi = [i for i, v in enumerate(h) if v == max(h)]

w = [0]*W
for i in range(M):
    w[G[i][1]-1] += 1
w_max = max(w)
w_mi = [i for i, v in enumerate(w) if v == max(w)]

cnt = h_max + w_max

T = []
for i in h_mi:
    for j in w_mi:
        t = [i+1, j+1]
        T.append(t)

Flag = True
for i in T:
    if i not in G:
        Flag = False
if Flag:
    cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W, M = map(int,input().split())
R = [0] * H
C = [0] * W
S = set()
for _ in range(M):
    h, w = map(int,input().split())
    S.add((h-1, w-1))
    R[h-1] += 1
    C[w-1] += 1

r = max(R)
c = max(C)

for h in [i for i in range(H) if R[i] == r]:
    for w in [i for i in range(W) if C[i] == c]:
        if not (h, w) in S:
            print(r + c)
            sys.exit()

print(r + c - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hn = {}
wn = {}
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  if (h,w) not in flag: 
    if h in hn:
      hn[h] += 1
    else:
      hn[h] = 1
    if w in wn:
      wn[w] += 1
    else:
      wn[w] = 1
  flag.add((h,w))
  
hrank = sorted(hn.items(), key=lambda t:-t[1])
wrank = sorted(wn.items(), key=lambda t:-t[1])

hmax = hrank[0][1]
wmax = wrank[0][1]

hmaxlist =[]
for k,v in hrank:
  if v == hmax:
    hmaxlist.append(k)
  else:
    break

wmaxlist =[]
for k,v in wrank:
  if v == wmax:
    wmaxlist.append(k)
  else:
    break

flag2 = set()
for i in hmaxlist:
  for j in wmaxlist:
    flag2.add((i,j))

if len(flag2 - flag) == 0:
  print(hmax+wmax -1)
else:
  print(hmax+wmax)

Submission status: Time Limit Exceeded

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

maxh = max(h)
maxw = max(w)

listh = [i for i, v in enumerate(h, 1) if v == maxh]
listw = [j for j, v in enumerate(w, 1) if v == maxw]

b = [(i, j) for i in listh for j in listw if (i, j) not in Mem]

if len(b):
  ans = maxh + maxw
else:
  ans = maxh + maxw - 1

print(ans)