Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

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

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

1 \leq h_i \leq H

1 \leq w_i \leq W

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

Input

Input is given from Standard Input in the following format:

H W M
h_1 w_1
\vdots
h_M w_M

Output

Print the answer.

Sample Input 1

2 3 3
2 2
1 1
1 3

Sample Output 1

3

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

Sample Input 2

3 3 4
3 3
3 1
1 1
1 2

Sample Output 2

3

Sample Input 3

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

Sample Output 3

6



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


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:

import glob
import os
import numpy as np

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:
    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index - 1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        H, W, M = map(int, self.input_data().split())
        B = [None for i in range(M)]

        ver_num =[0 for i in range(W+1)] # 列ごとの合計(行分ある)
        hol_num = [0 for i in range(H+1)] # 行ごとの合計(列分ある)

        for i in range(M):
            B[i] = list(map(int, self.input_data().split()))
            ver_num[B[i][1]] +=1
            hol_num[B[i][0]] +=1

        ver_max = np.max(np.array(ver_num))
        hol_max = np.max(np.array(hol_num))

        max_columns = []
        max_rows = []

        for i in range(1,W+1):
            if ver_max == ver_num[i]:
                max_columns.append(i)
        for i in range(1,H+1):
            if hol_max == hol_num[i]:
                max_rows.append(i)

        result = ver_max + hol_max - 1
        for c in max_columns:
            for r in max_rows:
                if [r,c] not in B:
                    result = ver_max + hol_max
                    break
                else:
                    pass

        print(str(result))

solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs =[]
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.append((x-1,y-1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]
    
    

    

    bh_destroy = bomb_most_h[1]
    

    bw_destroy = bomb_most_w[1]
    

    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    
    ans = 0
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if [bh,bw] in BOMB_HW:
                ans = max(bh_destroy+bw_destroy-1,ans)
            else:
                ans = max(bh_destroy+bw_destroy,ans)
    print(ans)
    


if __name__ == '__main__':
    main()

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 len(plot[i])==0:
          u+=0
        else:
          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:
import sys

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

h_count = {}
w_count = {}
for h,w in hw:
    if h in h_count:
        h_count[h] += 1
    else:
        h_count[h] = 1
    if w in w_count:
        w_count[w] += 1
    else:
        w_count[w] = 1

max_h = max(h_count.values())
max_w = max(w_count.values())
ans = max_h + max_w

max_h_list = [k for k,v in h_count.items() if v == max_h]
max_w_list = [k for k,v in w_count.items() if v == max_w]

num = 0
for h,w in hw:
    if h in max_h_list and w in max_w_list:
        num += 1

if num < len(max_h_list)*len(max_w_list):
    print(ans)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

pas = 0

H, W, M = map(int, input().split())
hn = []
wn = []
tli = []
for _ in range(M):
    h, w = map(int, input().split())
    tli.append([h,w])
    hn.append(h)
    wn.append(w)

hcnt = Counter(hn)
wcnt = Counter(wn)

ha, cha = zip(*hcnt.most_common())
wa, cwa = zip(*wcnt.most_common())

hli = [int(ha[0])]
wli = [int(wa[0])]
for i in range(len(cha)-1):
    if cha[i] == cha[i+1]:
        hli.append(int(ha[i+1]))
    else:
        break
for i in range(len(cwa)-1):
    if cwa[i] == cwa[i+1]:
        wli.append(int(wa[i+1]))
    else:
        break

for i in range(len(hli)):
    if pas == 1:
        break
    for k in range(len(wli)):
        if [hli[i], wli[k]] not in tli:
            ans = cha[i] + cwa[k]
            pas = 1
            break

if pas == 0:
    print(cha[0] + cwa[0] - 1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int, input().split())
pos = [['.' for i in range(w)] for j in range(h)]
row = [0]*h
col = [0]*w
for i in range(m):
    r,c = map(int,input().split())
    pos[r-1][c-1] = '*'
    row[r-1] += 1
    col[c-1] += 1
targets = max(col)+max(row)

flag = 0
if max(row) > max(col):
    for i in range(len(col)):
        if col[i] == max(col):
            if pos[row.index(max(row))][i] == '.':
                flag = 1
else:
    for i in range(len(row)):
        if row[i] == max(row):
            if pos[i][col.index(max(col))] == '.':
                flag = 1
if flag == 0:
    targets -= 1
print(targets)

Submission status: Time Limit Exceeded

Solution code:
h, w, m = map(int, input().split())
s = [[False] * w for _ in range(h)]
num_h = [0] * h
num_w = [0] * w
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    s[hi][wi] = True
    num_h[hi] += 1
    num_w[wi] += 1
max_h_list = []
max_h_val = 0
max_w_list = []
max_w_val = 0
for hi in range(h):
    if num_h[hi] > max_h_val:
        max_h_list = [hi]
        max_h_val = num_h[hi]
    elif num_h[hi] == max_h_val:
        max_h_list.append(hi)
for wi in range(w):
    if num_w[wi] > max_w_val:
        max_w_list = [wi]
        max_w_val = num_w[wi]
    elif num_w[wi] == max_w_val:
        max_w_list.append(wi)

for max_hi in max_h_list:
    for max_wi in max_w_list:
        if s[max_hi][max_wi] == False:
            print(max_h_val + max_w_val)
            exit()
print(max_h_val + max_w_val - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int, input().split())
nrow=[0]*H
ncol=[0]*W
xycoord=[]

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

#ncol=collections.Counter(xcoord)
#nrow=collections.Counter(ycoord)

row_cand=set([i for i, x in enumerate(nrow) if x == max(nrow)])
col_cand=set([i for i, x in enumerate(ncol) if x == max(ncol)])


flag=0
for i in xycoord:
	if (i[0] in col_cand) and (i[1] in row_cand):
		flag+=1

if flag<(len(col_cand)*len(row_cand)):
	print(max(nrow)+max(ncol))
else:
	print(max(nrow)+max(ncol)-1)



# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
d = defaultdict(list)

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    d[h-1].append(w-1)
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

maxi = 0
for i in hlist:
    for j in wlist:
        ans = maxh + maxw
        if j in d[i]:
            ans -= 1
        maxi = max(maxi,ans)
        # print(maxi)
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int,input().rstrip().split())
main=[list(map(int,input().split())) for i in range(m)]
hmax=0
wmax=0
dph=[0 for i in range(h)]
dpw=[0 for i in range(w)]
for i in main:
    dph[i[0]-1]+=1
    dpw[i[1]-1]+=1
hpoint=[]
wpoint=[]
for i in range(1,h+1):
    if hmax<dph[i-1]:
        hpoint.clear()
        hpoint.append(i)
        hmax=dph[i-1]
    elif hmax==dph[i-1]:
        hpoint.append(i)
for i in range(1,w+1):
    if wmax<dpw[i-1]:
        wpoint.clear()
        wpoint.append(i)
        wmax=dpw[i-1]
    elif wmax==dpw[i-1]:
        wpoint.append(i)

last=[]
for i in hpoint:
    for j in wpoint:
        last.append([i,j])
flag=0
for i in last:
    mini=0
    for j in main:
        if j==i:
            mini=1
    if mini==0:
        flag=1
        break
if flag==0:
    print(hmax+wmax-1)
else:
    print(hmax+wmax)

Submission status: Time Limit Exceeded

Solution code:
import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
B = [[0 for i in range(W)] for j in range(H)] ##掛け算で書いてはいけない

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
    B[hi-1][wi-1]=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        if B[h_max[ii]][w_max[jj]]==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        h_cand=[k for k, v in enumerate(h) if v == h_max[ii]+1]
        w_cand=[l for l, v in enumerate(w) if v == w_max[jj]+1]
        h_set = set(h_cand)
        w_set = set(w_cand)
        matched_list = list(h_set & w_set)
        #print(h_cand,w_cand)
        #print(matched_list)
        if len(matched_list)==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''

Submission status: Time Limit Exceeded

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

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1
        c[x[0]][x[1]] = 1

    my = max(ay)
    mx = max(ax)
    by = [i for i, x in enumerate(ay) if x == my]
    bx = [i for i, x in enumerate(ax) if x == mx]

    ans = my + mx
    tmp = 1
    if len(by)*len(bx) > m:
        tmp = 0
    else:
        for y in by:
            for x in bx:
                if c[y][x] == 0:
                    tmp = 0
                    break
            else:
                continue
            break
    print(ans - tmp)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
HW_L = [[int(x)-1 for x in input().split()] for y in range(M)]

w_l = [0] * W
h_l = [0] * H

for _hi, _wi in HW_L:
    w_l[_wi] += 1
    h_l[_hi] += 1

h_idx = [i for i, x in enumerate(h_l) if x == max(h_l)]
w_idx = [i for i, x in enumerate(w_l) if x == max(w_l)]

for hi in h_idx:
    for wj in w_idx:
        if [hi, wj] in HW_L:
            continue
        else:
            print(max(h_l) + max(w_l))
            exit(0)

print(max(h_l) + max(w_l)-1)

Submission status: Time Limit Exceeded

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

h=[0]*H
w=[0]*W

for i in range(M):
    h[(AA[i][0]-1)]+=1
    w[(AA[i][1]-1)]+=1
max_h=max(h)
max_w=max(w)

X=[i for i, x in enumerate(h) if x == max_h]
Y=[i for i, x in enumerate(w) if x == max_w]

for i,j in itertools.product(X,Y):
    if [i+1,j+1] in AA:
        flag=1
    else:
        flag=0
        break
print(max_h+max_w-flag)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M= map(int,readline().split())
h_cnt = [0]*(H+1)
w_cnt = [0]*(W+1)
data = [[False]*(W+1) for i in range(H+1)]

for i in range(M):
    h,w = map(int,readline().split())
    data[h][w] = True
    h_cnt[h] += 1 
    w_cnt[w] += 1
    
max_h = max(h_cnt)
max_w = max(w_cnt)

max_h_ind = []
max_w_ind = []
max_h_cnt = 0
max_w_cnt = 0

for i in range(H+1):
    if max_h == h_cnt[i]:
        max_h_cnt += 1
        max_h_ind.append(i)

for i in range(W+1):
    if max_w == w_cnt[i]:
        max_w_cnt += 1
        max_w_ind.append(i)
max_h_ind = set(max_h_ind)
max_w_ind = set(max_w_ind)

t = list(itertools.product(max_h_ind, max_w_ind))

if max_w_cnt * max_h_cnt > M:
    print(max_h+max_w)
else:
    for h,w in t:
        if data[h][w] == False:
            print(max_h+max_w)
            sys.exit()
    print(max_h+max_w-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
cntH = {}
cntW = {}
tot = set()
for i in range(M):
    h, w = map(int, input().split())
    tot.add((h-1,w-1))
    if h-1 in cntH:
        cntH[h-1] += 1
    else:
        cntH[h-1] = 1
    if w-1 in cntW:
        cntW[w-1] += 1
    else:
        cntW[w-1] = 1
#print(cntH, cntW)
ma = 0
for u in cntH.keys():
    for v in cntW.keys():
        res = cntH[u] + cntW[v]
        if (u, v) in tot:
            res -= 1
        ma = max(ma, res)
print(ma)

Submission status: Time Limit Exceeded

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

cnt_h = [0] * h
cnt_w = [0] * w

for h1,w1 in hw:
    cnt_h[h1-1] += 1
    cnt_w[w1-1] += 1

lh = []
lw = []

max1 = 0

for i,e in enumerate(cnt_h):
    max1 = max(max1, e)
    if e == max1:
        lh.append((e,i))

max1 = 0
for i,e in enumerate(cnt_w):
    max1 = max(max1, e)
    if e == max1:
        lw.append((e,i))

lh.sort(reverse = True)
lw.sort(reverse = True)

mh = lh[0][0]
mw = lw[0][0]

idx_h = 0
idx_w = 0

cnt = 0
for i,j in lh:
    if i == mh:
        cnt += 1
    else:
        break

idx_h = cnt

cnt = 0
for i,j in lw:
    if i == mw:
        cnt += 1
    else:
        break

idx_w = cnt

ans = mh + mw

v = [[False] * w for _ in range(h)]
for h1,w1 in hw:
    v[h1-1][w1-1] = True

if idx_h * idx_w > m:
    print(ans)
    exit()

for i in range(idx_h):
    for j in range(idx_w):
        if not v[lh[i][1]][lw[j][1]]:
            print(ans)
            exit()

print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
H, W, M = map(int, input().split())
bombw = [0 for _ in range(W)]
bombh = [0 for _ in range(H)]
field = [[False for _ in range(W)] for _ in range(H)]

for i in range(M):
    h, w = map(int, input().split())
    field[h - 1][w - 1] = True
    bombw[w - 1] += 1
    bombh[h - 1] += 1

maxw = [i for i, x in enumerate(bombw) if x == max(bombw)]
maxh = [i for i, x in enumerate(bombh) if x == max(bombh)]
# print(maxw, maxh)

for i in maxw:
    for j in maxh:
        if not field[j][i]:
            print(max(bombw) + max(bombh))
            exit()

print(max(bombw) + max(bombh) - 1)

# for i in field:
#     print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math
import itertools


def I(): return int(sys.stdin.readline().rstrip())
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())


def main():
    H, W, M = LI()

    HList = [0]*H
    WList = [0]*W
    graph = [[0 for _ in range(W)] for _ in range(H)]

    for m in range(M):
        h, w = LI()
        HList[h-1] += 1
        WList[w-1] += 1
        graph[h-1][w-1] += 1

    Hmax = max(HList)
    Wmax = max(WList)

    HIndex = [i for i, v in enumerate(HList) if v == Hmax]
    WIndex = [i for i, v in enumerate(WList) if v == Wmax]

    ans = Hmax + Wmax
    for h in HIndex:
        for w in WIndex:
            if graph[h][w] == 0:
                print(ans)
                return

    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

H,W,M = (int(x) for x in input().rstrip('\n').split())
ds = []
for _ in range(M):
  h,w = (int(x) for x in input().rstrip('\n').split())
  ds.append([h,w])
dh = Counter([x[0] for x in ds])
dw = Counter([x[1] for x in ds])
mh = dh.most_common()[0][1]
mw = dw.most_common()[0][1]
max_h = [k for k,v in dh.items() if v==mh]
max_w = [k for k,v in dw.items() if v==mw]
check = 0
for x in max_w:
  if check > 0:
    break
  for y in max_h:
    if [y,x] not in ds:
      check += 1
      break
if check ==0:
  print(mh+mw-1)
else:
  print(mh+mw)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

y_to_num = defaultdict(int)
x_to_num = defaultdict(int)

# y_indexes = set()
# x_indexes = set()
y_to_sum = defaultdict(set)


for _ in range(m):
    hh, ww = map(lambda x: int(x), input().split())
    y_to_num[hh] += 1
    x_to_num[ww] += 1
    
    y_to_sum[hh].add(hh + ww)
    
# print(y_to_num, x_to_num)
    
# for y, num_y in y_to_num:
#     for x, num_x in x_to_num:

max_num = 0
  
for y in range(h):
    for x in range(w):
        num = y_to_num[y+1] + x_to_num[x+1]
        if x+y+2 in y_to_sum[y+1]:
            num -= 1
        max_num = max(max_num, num)
        
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools
import numpy as np


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    H, W, M = list(map(int, input().split()))
    B = []
    I, R = {}, {}
    for m in range(M):
        h_m, w_m = list(map(int, input().split()))
        B.append((h_m, w_m))
        if h_m in I.keys():
            I[h_m].append(w_m)
        else:
            I[h_m] = [w_m]
        if w_m in R.keys():
            R[w_m].append(h_m)
        else:
            R[w_m] = [h_m]

    return H, W, M, B, I, R


def main(H: int, W: int, M: int, B: list, I: dict, R: dict) -> None:
    # 求解処理
    h_bom = []
    max_bom_h = 0
    for h in I.keys():
        bom_h = len(I[h])
        if max_bom_h == bom_h:
            h_bom.append(h)
            continue
        if max_bom_h < bom_h:
            max_bom_h = bom_h
            h_bom = [h]

    w_bom = []
    max_bom_w = 0
    for w in R.keys():
        bom_w = len(R[w])
        if max_bom_w == bom_w:
            w_bom.append(w)
            continue
        if max_bom_w < bom_w:
            max_bom_w = bom_w
            w_bom = [w]

    can_separate = False
    for h_b, w_b in itertools.product(h_bom, w_bom):
        if (h_b, w_b) not in B:
            can_separate = True
            break

    ans = max_bom_h + max_bom_w
    if not can_separate:
        ans -= 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    H, W, M, B, I, R = get_input()

    # メイン処理
    main(H, W, M, B, I, R)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def sol(H,W,tar,row,col,res):
    for i in range(H):
        for j in range(W):
            res = max(res,row[i]+col[j]-tar[i,j])
    return res


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

    tar = np.array([[0 for j in range(W)] for i in range(H)])
    row = np.array([0 for i in range(H)])
    col = np.array([0 for j in range(W)])

    for i in range(M):
        h,w = map(int,input().split())
        tar[h-1,w-1] = 1
        row[h-1] += 1
        col[w-1] += 1

    res = sol(H,W,tar,row,col,0)

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
hallline = {}
for i in range(H):
    hallline[i] = 0
wallline = {}
for j in range(W):
    wallline[j] = 0
b = [[False for i in range(W)] for j in range(H)]

for i in range(M):
    tmp = list(map(lambda x: int(x) - 1, input().split()))
    hallline[tmp[0]] += 1
    wallline[tmp[1]] += 1
    b[tmp[0]][tmp[1]] = True

t = max(hallline.values())
s = max(wallline.values())

hkeys = [k for k, v in hallline.items() if v == t]
wkeys = [k for k, v in wallline.items() if v == s]

for i in hkeys:
    for j in wkeys:
        if not b[i][j]:
            print(t + s)
            exit()
print(t + s - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW.append([h,w])

#print(Y,X)

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)


#print(LY,LX)
import sys
for i in range(len(LY)):
    for j in range(len(LX)):
        if [LY[i],LX[j]] not in HW:
            print(MY+MX)
            sys.exit()
print(MY+MX-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w,m = get_nums_l()
    targets = []
    H = []
    W = []
    for i in range(m):
        hi, wi = get_nums_l()
        H.append(hi-1)
        W.append(wi-1)
    
    rows = [0] * h
    cols = [0] * w

    for i in range(m):
        rows[H[i]] += 1
        cols[W[i]] += 1

    rmax = 0
    rmaxi = []
    for i,x in enumerate(rows):
        if x > rmax:
            rmax = x
            rmaxi = [i]
        elif x == rmax:
            rmaxi.append(i)
    cmax = 0
    cmaxi = []
    for i,x in enumerate(cols):
        if x > cmax:
            cmax = x
            cmaxi = [i]
        elif x == cmax:
            cmaxi.append(i)

    log(rmax,cmax)
    log(rmaxi, cmaxi)

    for rmi in rmaxi:
        for cmi in cmaxi:
            ok = True
            for i in range(m):
                if H[i] == rmi and W[i] == cmi:
                    ok = False
                    break
            if ok:
                print(rmax + cmax)
                return

    print(rmax + cmax - 1)

main()

Submission status: Time Limit Exceeded

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

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

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



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

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

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

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

    res = 0
    for item in max_col_index:
        for jtem in max_row_index:
            if grid[item][jtem] == 1:
                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:
import itertools
import sys
input = sys.stdin.readline

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 n1, n2 in itertools.product(hmax_ind, wmax_ind):
  res.append(str(n1)+"_"+str(n2))

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())
h = []
for i in range(M):
    h.append(list(map(int,input().split())))
bomb_possible_tate = []
bomb_possible_yoko = []
t = 0
s = 0
    
for i in range(H):
    for k in range(M):
        if h[k][0] == i+1:
            t += 1
        else:
            pass
    bomb_possible_tate.append(t)
    t = 0
    
for j in range(W):
    for k in range(M):
        if h[k][1] == j+1:
            s += 1
        else:
            pass
    bomb_possible_yoko.append(s)
    s = 0


max_tate = max(bomb_possible_tate)
max_yoko = max(bomb_possible_yoko)

tate_koho = [i+1 for i, v in enumerate(bomb_possible_tate) if v == max(bomb_possible_tate)]
yoko_koho = [i+1 for i, v in enumerate(bomb_possible_yoko) if v == max(bomb_possible_yoko)]
koho = []

for i in range(len(tate_koho)):
    for j in range(len(yoko_koho)):
        koho.append([tate_koho[i],yoko_koho[j]])
        
a = 0

for i in range(len(koho)):
    for j in range(M):
        if koho[i] == h[j]:
            a += 1
        else:
            pass
        
if a == len(koho):
    print(max_tate + max_yoko - 1)
else:
    print(max_tate + max_yoko)

Submission status: Time Limit Exceeded

Solution code:
import collections
H,W,M = map(int, input().split())
hw = [map(int, input().split()) for _ in range(M)]
h, w = [list(i) for i in zip(*hw)]


nyuuryoku_set = set(zip(h, w))

ch = collections.Counter(h)
cw = collections.Counter(w)
ch_zyunn = ch.most_common()
cw_zyunn = cw.most_common()


result = ch_zyunn[0][1] + cw_zyunn[0][1]
#重複チェックをする
ch_max = [i[0] for i in ch.items() if i[1] >= ch_zyunn[0][1]]
cw_max = [i[0] for i in cw.items() if i[1] >= cw_zyunn[0][1]]

flg = True
for i in range(len(ch_max)):
    for j in range(len(cw_max)):
        if ((ch_max[i],cw_max[j]) in nyuuryoku_set):
            continue
        else:
          flg = False  
if flg:
    print(result-1)
else:
    print(result)

Submission status: Time Limit Exceeded

Solution code:
#from functools import lru_cache
import sys
from itertools import product,combinations
from functools import reduce,lru_cache
import heapq

def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def list_t(l): return vfunc(lambda *args:args)(*l)

def rvfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:rvfunc(f)(*x,**kwargs) if all(vfunc(lambda y:isinstance(y,list))(x)) else f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

s=rvfunc(int)(reader())
h,w,m=s[0]
hl,wl = [0]*h,[0]*w
hw=s[1:]
hh,ww = list_t(hw)
for i in range(len(hw)):
    hl[hh[i]-1]+=1
    wl[ww[i]-1]+=1
hlmax,wlmax = vfunc(max)([hl,wl])
hlidx = tuple(filter(lambda a:hl[a]==hlmax,range(len(hl))))
wlidx = tuple(filter(lambda a:wl[a]==wlmax,range(len(wl))))
minus = 1
if len(hlidx)*len(wlidx)>len(hw): minus=0
else:
    for i in hlidx:
        for j in wlidx:
            if not [i+1,j+1] in hw:
                minus=0
                break
#    fltd = tuple(filter(lambda a:a[0]-1 in hlidx and a[1]-1 in wlidx,hw))
#    if len(fltd)!=len(hlidx)*len(wlidx): minus=0
#print(fltd,hw)
# for i in hlidx:
#     for j in wlidx:
# #        print([i+1,j+1],fltd)
#         if not [i+1,j+1] in fltd:
#             minus=0
#             break
print(max(hl)+max(wl)-minus)