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  collections

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

H_count = collections.defaultdict(set)
W_count = collections.defaultdict(set)
for m in range(M):
    h, w = map(int, input().split())
    H_count[h].add(w)
    W_count[w].add(h)

max_count = 0

for h, w_list in H_count.items():
    for w, h_list in W_count.items():
        count = len(w_list) + len(h_list)
        if w in w_list or h in h_list:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h,w,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(m)]

hw_list = [[] for _ in range(h+1)]
wh_list = [[] for _ in range(w+1)]

for i,j in d:
    hw_list[i].append(j)
    wh_list[j].append(i)

h_cnt = []
w_cnt = []
for i in hw_list:
    h_cnt.append(len(i))

for i in wh_list:
    w_cnt.append(len(i))


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

ret = h_max + w_max
h_max_ids = []
w_max_ids = []
for i,v in enumerate(h_cnt):
    if v == h_max:
        h_max_ids.append(i)

for i,v in enumerate(w_cnt):
    if v == w_max:
        w_max_ids.append(i)

flg = False
for i in h_max_ids:
    target_w_list = hw_list[i]
    for j in w_max_ids:
        if j not in target_w_list:
            flg = True
            break
    if flg:
        break
if not flg:
    ret -=1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
inp=input().split(' ')
h=int(inp[0])
w=int(inp[1])
m=int(inp[2])

rows={}
cols={}
pts=[]

for _ in range(m):
    inp=input().split(' ')
    x=int(inp[0])
    y=int(inp[1])

    rows[x]=rows.get(x,0)+1
    cols[y]=cols.get(y,0)+1
    pts.append((x,y))

pts = set(pts)
ans=0

for i in range(1,h+1):
    for j in range(1, w+1):
        x=0
        x+=rows.get(i,0)
        x+=cols.get(j,0)
        if (i,j) in pts:
            x=x-1
        ans=max(ans,x)

print(ans)

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 = maxh+maxw-1
for i in hlist:
    for j in wlist:
        if j not in d[i]:
            maxi += 1
            print(maxi)
            exit()
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, M = map(int, input().split())
    S = []
    for i in range(M):
        S.append(list(map(int, input().split())))
    sums = 0
    current_top = 0
 
    for i in range(H):
        for j in range(W):
            sums = 0
            for k in range(len(S)):
                if S[k][0] == i+1 or S[k][1] == j+1:
                    sums += 1
            if sums > current_top:
                current_top = sums
            if current_top == M:
                print(current_top)
                return
    print(current_top)
    
main()

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)

Submission status: Time Limit Exceeded

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

bombDict = dict()
bombDictH = dict()
bombDictW = dict()


for i in range(h+1):
    bombDict[i] = set()
    bombDictH[i] = 0

for i in range(w+1):
    bombDictW[i] = 0


for i in range(m):
    bombH,bombW = list(map(int,input().split()))
    bombDictH[bombH] += 1
    bombDictW[bombW] += 1
    bombDict[bombH].add(bombW)

maxH = max(bombDictH,key = bombDictH.get)
maxW = max(bombDictW,key = bombDictW.get)
maxHV = max(bombDictH.values())
maxWV = max(bombDictW.values())

hList = list(bombDictH.values())
wList = list(bombDictW.values())

maxHList = []
maxWList = []

if hList.count(maxHV) > 1:
    for i in range(h+1):
        if hList[i] == maxHV:
            maxHList.append(i)
else:
    maxHList.append(maxH)

if wList.count(maxWV) > 1:
    for i in range(w+1):
        if wList[i] == maxWV:
            maxWList.append(i)
else:
    maxWList.append(maxW)

ans = 0

for i in maxHList:
    for j in maxWList:
        if j in bombDict[i]:
            ans = max(ans,bombDictH[i] + bombDictW[j] - 1)
        else:
            ans = max(ans,bombDictH[i] + bombDictW[j])

print(ans)

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:
    B = tuple(B)
    # 求解処理
    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:
sum=0
i = list(map(int, input().split()))
H=i[0]
W=i[1]
N=i[2]
h=[0]*(H)
w=[0]*(W)
a = [[0 for j in range(W)] for i in range(H)]
for j in range(N):
    i = list(map(int, input().split()))
    h[i[0]-1]+=1
    w[i[1]-1]+=1
    a[i[0]-1][i[1]-1]=1
if max(h)>max(w):
    sum+=max(h)
    for i in range(W):
        if a[h.index(max(h))][i]==1:
            a[h.index(max(h))][i]=0
            w[i]-=1
    print(sum+max(w))
else:
    sum+=max(w)
    for i in range(H):
        if a[i][w.index(max(w))]==1:
            a[i][w.index(max(w))]=0
            h[i]-=1
    print(sum+max(h))

Submission status: Time Limit Exceeded

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


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


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


def bis_exist(lis,dev):
    a=0
    b=len(lis)-1
    if lis[b]==dev:
        return 1
    while a<b:
        c=(a+b)//2
        if lis[c]==dev:
            return 1
        if comp(lis[c],dev)==1:
            a=c+1
        if comp(lis[c],dev)==-1:
            b=c
    return 0


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

Submission status: Time Limit Exceeded

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    (h, w, m) = [int(e) for e in lines[0].split(" ")]
    hw = []
    for i in range(1, m + 1):
        hw.append([int(e) - 1 for e in lines[i].split(" ")])

    return (h, w, m, hw)

def solve(h, w, m, hw):

    d = dict()
    for e in hw:
        d[(e[0], e[1])] = 1

    current = 0

    d_total_i = dict()
    for i in range(h):

        total_i = 0
        for k in range(w):
            total_i = total_i + d.get((i, k), 0)

        d_total_i[i] = total_i

    d_total_j = dict()
    for j in range(w):
        
        total_j = 0
        for l in range(h):
            total_j = total_j + d.get((l, j), 0)

        d_total_j[j] = total_j



    for i in range(h):
        for j in range(w):

            total = d_total_i[i] + d_total_j[j]           

            if d.get((i, j)) == 1:
                total = total - 1

            if total > current:
                current = total

    return current



def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, M = LI()
    hw = [LI() for _ in range(M)]
    hw_set = set([(h, w) for h, w in hw])

    cnt_h = collections.Counter([h for h, w in hw])
    cnt_w = collections.Counter([w for h, w in hw])

    # i行目にはどの列にあります
    # print(cnt_h)
    # print(cnt_w)
    max_h = max(cnt_h.values())
    max_w = max(cnt_w.values())
    max_h_k = [k for k, v in cnt_h.items() if v == max_h]
    max_w_k = [k for k, v in cnt_w.items() if v == max_w]
    is_on_target = True
    for i, j in itertools.product(max_h_k, max_w_k):
        if (i, j) not in hw_set:
            is_on_target = False

    if is_on_target:
        ans = max(cnt_h.values()) + max(cnt_w.values()) - 1
    else:
        ans = max(cnt_h.values()) + max(cnt_w.values())
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

tate=[]
yoko=[]

for i in range(m):
    tate.append(hw[i][0])
    yoko.append(hw[i][1])

from collections import Counter
tatec=Counter(tate).most_common()
yokoc=Counter(yoko).most_common()

c_1_max=tatec[0][1]
c_1s=[]
for t in tatec:
    if t[1]==c_1_max:
        c_1s.append(t[0])
    else:
        break

c_2_max=yokoc[0][1]
c_2s=[]
for y in yokoc:
    if y[1]==c_2_max:
        c_2s.append(y[0])
    else:
        break

flag=False

for c_1 in c_1s:
    for c_2 in c_2s:
        tmp_flag=0
        for i in range(m):
            h_i=hw[i][0]
            w_i=hw[i][1]
            if h_i!=c_1 or w_i!=c_2:
                tmp_flag+=1
        if tmp_flag==m:
            flag=True
        if flag:
            break
    if flag:
        break

print(max(tatec[0][1]+yokoc[0][1], 1) if flag else max(tatec[0][1]+yokoc[0][1]-1, 1))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
H, W, M = map(int, input().split())
MASU = [[0 for i in range(W)]for j in range(H)]
hcount = [0]*H
wcount = [0]*W
for i in range(M):
    h, w = map(int, input().split())
    MASU[h-1][w-1] = 1
    hcount[h-1] += 1
    wcount[w-1] += 1
hmax = max(hcount)
wmax = max(wcount)
ans = hmax+wmax



Hkouho = []
Wkouho = []
for i in range(H):
    if hcount[i] == hmax:
        Hkouho.append(i)
for i in range(W):
    if wcount[i] == wmax:
        Wkouho.append(i)
ans -= 1
for i in Hkouho:
    for j in Wkouho:
        if MASU[i][j] == 0:
            ans += 1
            print(ans)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

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

#dic[row, col] -> set(ids)
h_dic = dd(set)
w_dic = dd(set)
spot = set()

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

#H_lis -> [i, num_spot(int)]
H_lis = []
for key, val in h_dic.items():
    H_lis.append([key, len(val)])
W_lis = []
for key, val in w_dic.items():
    W_lis.append([key, len(val)])
H_lis.sort(key=lambda x: x[1], reverse=True)
W_lis.sort(key=lambda x: x[1], reverse=True)

#print(H_lis, W_lis)
max_h_num = H_lis[0][1]
#print(max_h)
max_w_num = W_lis[0][1]

ans = 0
max_h_lis = [val[0] for val in H_lis if val[1] == max_h_num]
max_w_lis = [val[0] for val in W_lis if val[1] == max_w_num]
for i in max_h_lis:
    for j in max_w_lis:
        count = max_h_num + max_w_num
        if (i, j) in spot:
            count -= 1
        ans = max(ans, count)
print(ans)

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

"""

Submission status: Time Limit Exceeded

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

tate = [0]*(w+1)
yoko = [0]*(h+1)

for i in range(m):
    yoko[hw[i][0]] += 1
    tate[hw[i][1]] += 1
    
ans = 0

t_max = -1


for i in range(1,w+1):
    if t_max < tate[i]:
        t_max = tate[i]
        t_max_idx = []
        t_max_idx.append(i)
    elif t_max == tate[i]:
        t_max_idx.append(i)

y_max = -1

for i in range(1,h+1):
    if y_max < yoko[i]:
        y_max = yoko[i]
        y_max_idx = []
        y_max_idx.append(i)
    elif y_max == yoko[i]:
        y_max_idx.append(i)
        
#s_y = set(y_max_idx)
#s_t = set(t_max_idx)

if len(y_max_idx)*len(t_max_idx) > m:
    print(t_max+y_max)
else:
    ans = 0
    for i in range(m):
        if hw[i][0] in y_max_idx and hw[i][1] in t_max_idx:
            ans += 1
    if ans < len(y_max_idx)*len(t_max_idx):
        print(t_max+y_max)
    else:
        print(t_max+y_max-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(330000)]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW[h].append(w)

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)

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

Submission status: Time Limit Exceeded

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

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_hw = [[] for _ in range(h+1)]

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_hw[h].append(w)

m_h = max(l_h)
m_w = max(l_w)

ans = m_h + m_w

l_h_2 = my_index_multi(l_h,m_h)
l_w_2 = my_index_multi(l_w,m_w)

flag = False

for i in l_h_2:
    for j in l_w_2:
        if j not in l_hw[i]:
            flag = True
            break
    if flag:
        break
else:
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

tate=[]
yoko=[]

for i in range(m):
    tate.append(hw[i][0])
    yoko.append(hw[i][1])

from collections import Counter
tatec=Counter(tate).most_common()
yokoc=Counter(yoko).most_common()

c_1_max=tatec[0][1]
c_1s=[]
for t in tatec:
    if t[1]==c_1_max:
        c_1s.append(t[0])
    else:
        break

c_2_max=yokoc[0][1]
c_2s=[]
for y in yokoc:
    if y[1]==c_2_max:
        c_2s.append(y[0])
    else:
        break

flag=False

for c_1 in c_1s:
    for c_2 in c_2s:
        tmp_flag=0
        for i in range(m):
            h_i=hw[i][0]
            w_i=hw[i][1]
            if h_i!=c_1 or w_i!=c_2:
                tmp_flag+=1
        if tmp_flag==m:
            flag=True
        if flag:
            break

print(max(tatec[0][1]+yokoc[0][1], 1) if flag else max(tatec[0][1]+yokoc[0][1]-1, 1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = [[0] * W for i in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    t[h-1][w-1] = 1
    h_t[h-1]+=1
    w_t[w-1]+=1
h_max = max(h_t)
h_max_list = [i for i in range(len(h_t)) if h_t[i] == h_max]
w_max = max(w_t)
w_max_list = [i for i in range(len(w_t)) if w_t[i] == w_max]

for h in h_max_list:
    for w in w_max_list:
        if t[h][w] == 0:
            print(h_max + w_max)
            exit()
print(h_max + w_max - 1)

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

    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:
h, w, m = map(int, input().split())
row_list = [0 for _ in range(h)]
col_list = [0 for _ in range(w)]
log = []

for i in range(m):
  hb, wb = map(int, input().split())
  log.append([hb-1, wb-1])
  row_list[hb-1] += 1
  col_list[wb-1] += 1

r_max_val = max(row_list)
c_max_val = max(col_list)
r_max_idx = []
for i in range(h):
  if row_list[i] == r_max_val:
    r_max_idx.append(i)
c_max_idx = []
for i in range(w):
  if col_list[i] == c_max_val:
    c_max_idx.append(i)

flag = False
for ri in r_max_idx:
  for ci in c_max_idx:
    tmp_flag = True
    for i in range(m):
      hb, wb = log[i]
      if ci == wb and ri == hb:
        tmp_flag = False
    if tmp_flag:
      flag = True
      break
  if flag:
    break
if flag:
  print(r_max_val + c_max_val)
else:
  print(r_max_val + c_max_val - 1)

Submission status: Time Limit Exceeded

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

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(hs) < len(ws):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break

else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import groupby


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(ll):
    return sum(1 for _ in ll)


def solve():
    H, W, M = read_ints()
    hw = []
    for _ in range(M):
        hw.append(read_ints())
    hw.sort()

    max_ws = {}
    max_count_ws = 0
    for h, ws in groupby(hw, key=lambda pair: pair[0]):
        ws = list(ws)
        max_count_ws = max(max_count_ws, len(ws))
        max_ws[h] = [w for _, w in ws]

    ks = list(max_ws.keys())
    for k in ks:
        if len(max_ws[k]) < max_count_ws:
            del max_ws[k]

    hw.sort(key=lambda pair: pair[1])
    max_hs = {}
    max_count_hs = 0
    for w, hs in groupby(hw, key=lambda pair: pair[1]):
        hs = list(hs)
        max_count_hs = max(max_count_hs, len(hs))
        max_hs[w] = [h for h, _ in hs]

    ks = list(max_hs.keys())
    for k in ks:
        if len(max_hs[k]) < max_count_hs:
            del max_hs[k]

    counter = Counter()
    for v in max_hs.values():
        counter += Counter(v)
    for k in max_ws.keys():
        if counter[k] != len(max_hs):
            return max_count_ws+max_count_hs
    return max_count_ws+max_count_hs-1


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

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)
from numba import njit,i8


@njit
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:
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    h, w, m = LI()
    mat = [[0 for i in range(w+1)] for i in range(h+1)]
    hs = defaultdict(int)
    ws = defaultdict(int)
    for i in range(m):
        hi, wi = LI()
        mat[hi][wi] = 1
        hs[hi] += 1
        ws[wi] += 1

    hsums_top = []
    wsums_top = []

    maxh = 0
    for i, top in hs.items():
        if maxh == top:
            hsums_top.append(i)
        elif maxh < top:
            maxh = top
            hsums_top = [i]

    maxw = 0
    for i, top in ws.items():
        if maxw == top:
            wsums_top.append(i)
        elif maxw < top:
            maxw = top
            wsums_top = [i]

    if len(hsums_top) * len(wsums_top) > m:
        print(maxh + maxw)
        return
    for i in hsums_top:
        for j in wsums_top:
            if mat[i][j] == 0:
                print(maxh + maxw)
                return
    print(maxh + maxw - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

h_obj=[0]*(h+1)
w_obj=[0]*(w+1)
hw_grid=[]
for _ in range(m):
  li=list(map(int,input().split()))
  hw_grid.append(li)
  h_obj[li[0]]+=1
  w_obj[li[1]]+=1
  
def index_Multi(List,liter):
    #Listはリスト本体・literは検索したい文字
    index_L = []
    for val in range(0,len(List)):
        if liter == List[val]:
            index_L.append(val)
    return index_L
  
max_h=max(h_obj)
max_w=max(w_obj)

max_h_li=index_Multi(h_obj,max_h)
max_w_li=index_Multi(w_obj,max_w)

#print("max_w_li",max_w_li)
#print("max_h_li",max_h_li)
#print(hw_grid)

set_list=[]
for H in max_h_li:
  for W in max_w_li:
    set_list.append(str([H,W]))

hw_grid=[str(pair) for pair in hw_grid]

#print("set_list",set_list)
#print("hw_grid",hw_grid)

#print("set(set_list)-set(hw_grid)",list(set(set_list)-set(hw_grid)))

if len(set(set_list)-set(hw_grid)) !=0:
  print(max(h_obj)+max(w_obj))
else:
  print(max(h_obj)+max(w_obj)-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, M = map(int, input().split())
rows = {i: 0 for i in range(H)}
cols = {i: 0 for i in range(W)}
d = defaultdict(int)
for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    rows[h] += 1
    cols[w] += 1
    d[(h,w)] += 1
max_rows = [kv for kv in rows.items() if kv[1] == max(rows.values())]
max_cols = [kv for kv in cols.items() if kv[1] == max(cols.values())]
non_dup = False
ans = max_rows[0][1] + max_cols[0][1]
flg = False
for kh, vh in max_rows:
    for kw, vw in max_cols:
        if d[(kh, kw)] == 0:
            non_dup = True
            flg = True
            break
    if flg:
        break
if not non_dup:
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

h = []
w = []
point = []
for i in range(M):
    a, b = list(map(int, input().split()))

    h.append(a)
    w.append(b)
    point.append((a, b))

h_count = collections.Counter(h)
w_count = collections.Counter(w)

h_count_max = h_count.most_common()[0][1]
w_count_max = w_count.most_common()[0][1]


max = 0
for i in range(1, H + 1):
    if (h_count[i] != h_count_max):
        continue

    for j in range(1, W + 1):
        if (w_count[j] != w_count_max):
            continue

        count = h_count[i] + w_count[j]

        if ((i, j) in point):
            count = count - 1

        if (count > max):
            max = count


print(max)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int, input().split())
a = [0]*m
hc=[0 for i in range(w)]
wc=[0 for i in range(h)]
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[]
wk=[]
for i in range(len(hc)):
	if hc[i]==hcm:
		hk.extend([i])
for i in range(len(wc)):
	if wc[i]==wcm:
		wk.extend([i])
for i in range(len(hk)):
	for j in range(len(wk)):
		if [wk[j],hk[i]] not in a:
			print(hcm+wcm)
			exit()
print(hcm+wcm-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = [0] * (3 * (10 ** 5))
PW = [0] * (3 * (10 ** 5))
for i in range(M):
    h, w = li()
    PH[i] = h
    PW[i] = w

mh = max(PH, key=PH.count)
mw = max(PW, key=PW.count)

is_same = False
for i in range(M):
    if PH[i] == mh and PW[i] == mw:
        is_same = True
cnt = PH.count(mh) + PW.count(mw)
if is_same:
    cnt -= 1

print(cnt)