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 sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * h
    w_lis = [0] * w
    hw_lis = [] 
    for i in range(m):
        hh, ww = map(int,input().split())
        hh -= 1
        ww -= 1
        h_lis[hh] += 1
        w_lis[ww] += 1
        hw_lis.append((hh, ww))
    h_max_index = [i for i, h in enumerate(h_lis) if h == max(h_lis)]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max(w_lis)]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not (h_i, w_i) in hw_lis:
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * h
    w_lis = [0] * w
    hw_lis = [[] for i in range(h)] 
    for i in range(m):
        hh, ww = map(int,input().split())
        hh -= 1
        ww -= 1
        h_lis[hh] += 1
        w_lis[ww] += 1
        hw_lis[hh].append(ww)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max(h_lis)]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max(w_lis)]
    for h_i in h_max_index:
        hw_lis[h_i].sort()
        for w_i in w_max_index:
            if bisect_left(hw_lis[h_i], w_i) == bisect(hw_lis[h_i], w_i):
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
cnth = [[0, i] for i in range(H)]
cntw = [[0, i] for i in range(W)]
L = [[False for _ in range(W)] for _ in range(H)]
for _ in range(M):
    h, w = map(lambda x: int(x) - 1, input().split())
    cnth[h][0] += 1
    cntw[w][0] += 1
    L[h][w] = True
cnth.sort(reverse=True)
cntw.sort(reverse=True)
mh = set()
ph = cnth[0]
for h in cnth:
    if ph[0] == h[0]:
        mh.add(h[1])
    else:
        break
    ph = h
mw = set()
pw = cntw[0]
for w in cntw:
    if pw[0] == w[0]:
        mw.add(w[1])
    else:
        break
    pw = w
max = cnth[0][0] + cntw[0][0]
for h in mh:
    for w in mw:
        if not (L[h][w]):
            print(max)
            break
    else:
        continue
    break
else:
    print(max - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * h
    w_lis = [0] * w
    hw_lis = [] 
    for i in range(m):
        hh, ww = map(int,input().split())
        hh -= 1
        ww -= 1
        h_lis[hh] += 1
        w_lis[ww] += 1
        hw_lis.append((hh, ww))
    h_max_index = [i for i, h in enumerate(h_lis) if h == max(h_lis)]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max(w_lis)]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not ((h_i, w_i) in hw_lis):
                print(h_lis[h_i]+w_lis[w_i])
                sys.exit()
    print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, M = [int(s) for s in input().split()]
    cols = [0] * W
    rows = [0] * H
    bombs = set()
    for _ in range(M):
        x, y = [int(s)-1 for s in input().split()]
        bombs.add((x, y))
        cols[y] += 1
        rows[x] += 1

    sc = sorted([(c, i) for i, c in enumerate(cols)], reverse=True)
    sr = sorted([(c, i) for i, c in enumerate(rows)], reverse=True)
    best = 0
    for v1, c in sc:
        for v2, r in sr:
            if v1 + v2 < best:
                break
            score = v1 + v2
            if (r, c) in bombs:
                score -= 1
            best = max(best, score)
    print(best)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    if bomb.count([bh - 1,bw - 1]) == 0:
        bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(set(hcnt))
wmax = max(set(wcnt))
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W,M=map(int,input().split())#slow,行数H、列数W、爆弾数M
hcnt=[0]*H#何行目に何個あるか
wcnt=[0]*W#何列目に何個あるか
bomb=[]
cnt=0

for i in range(M):
    bh,bw=map(int,input().split())
    hcnt[bh-1]+=1#行方向
    wcnt[bw-1]+=1#列方向
    if bomb.count([bh-1,bw-1])==0:
        bomb.append([bh-1,bw-1])
hmax=max(set(hcnt))
wmax=max(set(wcnt))
for i in range(H):
    for j in range(W):
        if hcnt[i]==hmax and wcnt[j]==wmax and bomb.count([i,j])==0:
            cnt+=1

if cnt>0:
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    if bomb.count([bh - 1,bw - 1]) == 0:
        bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(set(hcnt))
wmax = max(set(wcnt))
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

Solution code:
[H, W, M] = list(map(int, input().split()))
i = [0]*H
j = [0]*W
hw = []


def lm(a, b):
    x = []
    for i in range(len(b)):
        if b[i] == a:
            x.append(i)
    return x


for x in range(M):
    [a, b] = list(map(int, input().split()))
    hw.append([a-1, b-1])
    i[a-1] += 1
    j[b-1] += 1

imax = max(i)
ilist = lm(imax, i)

jmax = max(j)
jlist = lm(jmax, j)

a = imax + jmax - 1

c=0
d=0
for I in ilist:
    for J in jlist:
        if [I, J] not in hw:
            a += 1
            c += 1
            break
    if c == 1:
        break
print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(set(hcnt))
wmax = max(set(wcnt))
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0 for i in range(H)]#何行目に何個あるか
wcnt = [0 for i in range(W)]#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

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

booms = [set() for _ in range(H)]

yoko = [0 for _ in range(W)]
tate = [0 for _ in range(H)]

for hw in hws:
    tate[hw[0]] += 1
    yoko[hw[1]] += 1
    booms[hw[0]].add(hw[1])
    
max_tate = max(tate)
max_yoko = max(yoko)


tate_candidates = []
yoko_candidates = []

for i in range(H):
    if tate[i] == max_tate:
        tate_candidates.append(i)
        
for i in range(W):
    if yoko[i] == max_yoko:
        yoko_candidates.append(i)

exist = 0
for tate_candidate in tate_candidates:
    for yoko_candidate in yoko_candidates:
        if yoko_candidate not in booms[tate_candidate]:
            exist = 1

print(max_tate + max_yoko + (exist-1))

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())#行数H、列数W、爆弾数M
hcnt = [0 for i in range(H)]#何行目に何個あるか
wcnt = [0 for i in range(W)]#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append([bh - 1,bw - 1])
hmax = max(hcnt)
wmax = max(wcnt)
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m=map(int, input().split())
xy = [map(int, input().split()) for _ in range(m)]
x, y = [list(i) for i in zip(*xy)]
ans=[]

for i in range(h):
    for j in range(w):
        counter=0
        for n in range(m):
            hx=x[n]
            hy=y[n]
            if hx==i+1 or hy==j+1:
                counter+=1
        ans.append(counter)

maxim=max(ans)
print(maxim)

Submission status: Time Limit Exceeded

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

dich={}
dicw={}
l=[]

for i in range(m):
  h,w=map(int,input().split())
  if h not in dich:
    dich[h]=1
  else:
    dich[h]+=1

  if w not in dicw:
    dicw[w]=1
  else:
    dicw[w]+=1
  
  l.append([h,w])
  
dicw=sorted(dicw.items(),key=lambda x:x[1],reverse=True)
dich=sorted(dich.items(),key=lambda x:x[1],reverse=True)

h_max=dich[0][1]
w_max=dicw[0][1]

ans=0
now=0
mae_h=h_max
mae_w=w_max

for i in range(len(dicw)):
  for j in range(len(dich)):
    nh=dich[j][1]
    nw=dicw[i][1]

    now=nh+nw
    if now<h_max+w_max:
      break

    if [dich[j][0],dicw[i][0]] in l:
      now-=1
    ans=max(ans,now)

    if h_max+w_max==ans:
      break
        
print(ans)

Submission status: Time Limit Exceeded

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

dich={}
dicw={}
l=[]

for i in range(m):
  h,w=map(int,input().split())
  if h not in dich:
    dich[h]=1
  else:
    dich[h]+=1

  if w not in dicw:
    dicw[w]=1
  else:
    dicw[w]+=1
  
  l.append([h,w])
  
dicw=sorted(dicw.items(),key=lambda x:x[1],reverse=True)
dich=sorted(dich.items(),key=lambda x:x[1],reverse=True)

h_max=dich[0][1]
w_max=dicw[0][1]

ans=0
now=0
mae_h=h_max
mae_w=w_max

for i in range(len(dicw)):
  for j in range(len(dich)):
    now=dicw[i][1]+dich[j][1]
    if now<mae_h+mae_w:
      break
    else:
      if [dich[j][0],dicw[i][0]] in l:
        now-=1
      ans=max(ans,now)
      mae_w=dicw[i][1]
      mae_h=dich[j][1]
      
print(ans)

Submission status: Time Limit Exceeded

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

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

for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    Y[h] += 1
    X[w] += 1
    Map.append((h, w))

MX = max(X)
MY = max(Y)
ans = MX + MY
Xans = []
Yans = []
for i, x in enumerate(X):
    if x == MX:
        Xans.append(i)
for i, y in enumerate(Y):
    if y == MY:
        Yans.append(i)
flag = False
cnt = 0
for h, w in Map:
    if h in Yans and w in Xans:
        cnt += 1
if cnt == len(Xans) * len(Yans):
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

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

h_max = max(h_list)
w_max = max(w_list)
h_max_list = set([i for i, v in enumerate(h_list) if v == max(h_list)])
w_max_list = set([i for i, v in enumerate(w_list) if v == max(w_list)])

place = len(h_max_list) * len(w_max_list)
candidate = 0
for h,w in target:
  if (h in h_max_list) and (w in w_max_list):
    candidate +=1

print(h_max+w_max-(place == candidate))

Submission status: Time Limit Exceeded

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

h_max = max(h_list)
w_max = max(w_list)
h_max_list = [i for i, v in enumerate(h_list) if v == max(h_list)]
w_max_list = [i for i, v in enumerate(w_list) if v == max(w_list)]

place = len(h_max_list) * len(w_max_list)
candidate = 0
for h,w in target:
  if (h in h_max_list) and (w in w_max_list):
    candidate +=1

print(h_max+w_max-(place == candidate))

Submission status: Time Limit Exceeded

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

h_max = max(h_list)
w_max = max(w_list)
h_max_list = [i for i, v in enumerate(h_list) if v == max(h_list)]
w_max_list = [i for i, v in enumerate(w_list) if v == max(w_list)]

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

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from numba import jit

def main(max_h,max_w,bomb_list,ans):
    count = len(max_h)*len(max_w)
    for mh in max_h:
        for mw in max_w:
            f=False
            for i in range(len(bomb_list)):
                if bomb_list[i][0]==mh and bomb_list[i][1]==mw:
                    f=True
                    break
            if not f:
                print(ans)
                return
                   
    print(ans-1)
    
def read_input():
    H,W,M = map(int,input().split())
    h={}
    w={}
    bomb_list=[]
    for i in range(M):
        ih,iw = map(int,input().split())
        bomb_list.append([ih,iw])
        if ih not in h:
            h[ih]=1
        else:
            h[ih]+=1
        if iw not in w:
            w[iw]=1
        else:
            w[iw]+=1
    max_h = [k for k, v in h.items() if v == max(h.values())]
    max_w = [k for k, v in w.items() if v == max(w.values())]
    return max_h,max_w,np.array(bomb_list),max(h.values())+max(w.values())

if __name__ == '__main__':
    max_h,max_w,bomb_list,ans = read_input()
    main(max_h,max_w,bomb_list,ans)

Submission status: Time Limit Exceeded

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


def read():
    H, W, M = map(int, input().strip().split())
    HW = []
    for i in range(M):
        h, w = map(int, input().strip().split())
        HW.append((h, w))
    return H, W, M, HW


def solve(H, W, M, HW):
    B = 10**6
    G = defaultdict(int)
    hcount = Counter()
    wcount = Counter()
    for h, w in HW:
        G[h*B+w] = 1
        hcount[h] += 1
        wcount[w] += 1
    hm = hcount.most_common()
    wm = wcount.most_common()
    hmax = hm[0][1]
    wmax = wm[0][1]
    
    ans = 0
    i = 0
    for hk, hv in hm:
        if hv < hmax:
            break
        for wk, wv in wm:
            if wv < wmax:
                break
            ans = max(ans, hmax + wmax - G[hk*B+wk])
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

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


def read():
    H, W, M = map(int, input().strip().split())
    HW = []
    for i in range(M):
        h, w = map(int, input().strip().split())
        HW.append((h, w))
    return H, W, M, HW


def solve(H, W, M, HW):
    G = [defaultdict(bool) for i in range(H+1)]
    hcount = Counter()
    wcount = Counter()
    for h, w in HW:
        G[h][w] = True
        hcount[h] += 1
        wcount[w] += 1
    hm = hcount.most_common()
    wm = wcount.most_common()
    hmax = hm[0][1]
    wmax = wm[0][1]
    
    ans = 0
    i = 0
    for hk, hv in hm:
        if hv  < hmax:
            break
        for wk, wv in wm:
            if wv < wmax:
                break
            ans = max(ans, hmax + wmax - G[hk][wk])
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

#import numpy as np
#import numba
#from numba import njit, b1, i4, i8, f8
#from numba import jit


def main():
    H,W,M = map(int,input().split())
    h={}
    w={}
    bomb_list=[]
    for i in range(M):
        ih,iw = map(int,input().split())
        bomb_list.append([ih,iw])
        if ih not in h:
            h[ih]=1
        else:
            h[ih]+=1
        if iw not in w:
            w[iw]=1
        else:
            w[iw]+=1

    max_h = [k for k, v in h.items() if v == max(h.values())]
    max_w = [k for k, v in w.items() if v == max(w.values())]

    count = len(max_h)*len(max_w)
    for th,tw in bomb_list:
        if th in max_h:
            if tw in max_w:
                count-=1
                if count<=0:
                    break
                   
    print(max(h.values())+max(w.values())+(-1 if count==0 else 0))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,m = list(map(int,input().split()))
rows = [0]*h
cols = [0]*w
bomb = [0]*m

for i in range(m):
    x,y = [int(i)-1 for i in input().split()]
    rows[x] += 1; cols[y] += 1
    bomb[i] = [x,y]

hmax = max(rows); wmax = max(cols); ans = hmax+wmax

hsearch = set(); wsearch = set()
for i in range(m):
    x,y = bomb[i]
    if rows[x] == hmax: hsearch.add(x)
    if cols[y] == wmax: wsearch.add(y)

if m < len(hsearch)*len(wsearch):
    flag = True
else:
    srows = list(hsearch)
    scols = list(wsearch)
    search_table = [[True for _ in range(len(scols))] for _ in range(len(srows))]
    for i in range(m):
        x,y = bomb[i]
        if x in srows and y in scols:
            search_table[srows.index(x)][scols.index(y)] = False

    flags = [True if sum(i)>0 else False for i in search_table]
    flag = any(flags)

print(ans if flag else ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W, M = map(int, input().split())
S = list(tuple(map(int, input().split())) for _ in range(M))
hh = dict()
ww = dict()
for i in range(M):
    h, w = S[i]
    if h in hh.keys():
        hh[h] += 1
    else:
        hh[h] = 1
    if w in ww.keys():
        ww[w] += 1
    else:
        ww[w] = 1
hhh = sorted(hh.items(), key=lambda x:x[1], reverse=True)
www = sorted(ww.items(), key=lambda x:x[1], reverse=True)
ans = hhh[0][1] + www[0][1]
if (hhh[0][0], www[0][0]) not in S:
    print(ans)
    sys.exit()
h = hhh[0][0]
for j in range(1, len(www)):
        if www[j][1] == www[j-1][1]:
            if (h, www[j][0]) not in S:
                print(ans)
                sys.exit()
        else:
            break
for i in range(1, len(hhh)):
    if hhh[i][1] == hhh[i-1][1]:
        h = hhh[i][0]
        if (h, www[0][0]) not in S:
            print(ans)
            sys.exit()
        for j in range(1, len(www)):
            if www[j][1] == www[j-1][1]:
                if (h, www[j][0]) not in S:
                    print(ans)
                    sys.exit()
            else:
                break
    else:
        break
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W, M = map(int, input().split())
S = list(tuple(map(int, input().split())) for _ in range(M))
hh = dict()
ww = dict()
for i in range(M):
    h, w = S[i]
    if h in hh.keys():
        hh[h] += 1
    else:
        hh[h] = 1
    if w in ww.keys():
        ww[w] += 1
    else:
        ww[w] = 1
hhh = sorted(hh.items(), key=lambda x:x[1], reverse=True)
www = sorted(ww.items(), key=lambda x:x[1], reverse=True)
ans = hhh[0][1] + www[0][1]
hhhh = deque([hhh[0][0]])
wwww = deque([www[0][0]])
for i in range(1, len(hhh)):
    if hhh[i][1] == hhh[i-1][1]:
        deque.append(hhhh, hhh[i][0])
    else:
        break
for i in range(1, len(www)):
    if www[i][1] == www[i-1][1]:
        deque.append(wwww, www[i][0])
    else:
        break
for h in hhhh:
    for w in wwww:
        if (h, w) not in S:
            print(ans)
            sys.exit()
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, M = map(int, input().split())
S = list(tuple(map(int, input().split())) for _ in range(M))
hh = dict()
ww = dict()
for i in range(M):
    h, w = S[i]
    if h in hh.keys():
        hh[h] += 1
    else:
        hh[h] = 1
    if w in ww.keys():
        ww[w] += 1
    else:
        ww[w] = 1
hhh = sorted(hh.items(), key=lambda x:x[1], reverse=True)
www = sorted(ww.items(), key=lambda x:x[1], reverse=True)
ans = hhh[0][1] + www[0][1]
hhhh = [hhh[0][0]]
wwww = [www[0][0]]
for i in range(1, len(hhh)):
    if hhh[i][1] == hhh[i-1][1]:
        hhhh.append(hhh[i][0])
    else:
        break
for i in range(1, len(www)):
    if www[i][1] == www[i-1][1]:
        wwww.append(www[i][0])
    else:
        break
for h in hhhh:
    for w in wwww:
        if (h, w) not in S:
            print(ans)
            sys.exit()
print(ans-1)

Submission status: Time Limit Exceeded

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

Hx=[] #爆破対象の座標を記録
Hy=[]
X=[]
for i in range(M):
    h,w=map(lambda x:int(x)-1,input().split())
    Hx.append(h)
    Hy.append(w)
    X.append([h,w])

sum_c=[0]*W #縦の合計
sum_r=[0]*H #横の合計
for i in Hy:
    sum_c[i] += 1
for j in Hx:
    sum_r[j] += 1

max_c=max(sum_c)
max_r=max(sum_r)

flag=0 #max_cの列とmax_rの行で交差点に爆弾がないところがあればflag=1
for i in range(H):
    for j in range(W):
        if sum_r[i]==max_r and sum_c[j]==max_c:
            if [i,j] not in X:
                flag=1
                break
    if flag==1:
        break

if flag==0:
    print(max_c+max_r-1)
else:
    print(max_c+max_r)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

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

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

x=min([min([mat[i][j] for j in cc]) for i in rr])

if x==0:
  print(r+c)
else:
  print(r+c-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

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

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

x=min(list(itertools.chain.from_iterable([[mat[i][j] for j in cc] for i in rr])))

if x==0:
  print(r+c)
else:
  print(r+c-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

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

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

x=sum([sum([mat[i][j] for j in cc]) for i in rr])

if x==len(rr)*len(cc):
  print(r+c-1)
else:
  print(r+c)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
row=[0]*H
col=[0]*W

mat=[[0 for i in range(W)] for j in range(H)]

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

r=max(row)
c=max(col)

rr=[i for i in range(H) if row[i]==r]
cc=[i for i in range(W) if col[i]==c]

for i in rr:
  for j in cc:
    if mat[i][j]==0:
      print(r+c)
      exit()

print(r+c-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
A=[]
B=[]
C=[]

for i in range(m):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append([a,b])

import collections
c = collections.Counter(A)
d = collections.Counter(B)

mc =c.most_common()[0][1]
md =d.most_common()[0][1]

A_T=[]
B_T=[]

for i in range(len(list(set(A)))):
    if c.most_common()[i][1]==mc:
        A_T.append(c.most_common()[i][0])
for i in range(len(list(set(B)))):
    if d.most_common()[i][1]==md:
        B_T.append(d.most_common()[i][0])

g =c.most_common()[0][1]+d.most_common()[0][1]
for p in range(len(A_T)):
    for k in range(len(B_T)):
        if [A_T[p],B_T[k]] not in C:
            print(g)
            exit()
print(g-1)

Submission status: Time Limit Exceeded

Solution code:
H,W,M = map(int, input().split())
width = [0]*W
height = [0]*H

st = set()
for i in range(M):
  y, x = map(int, input().split())
  st.add((x - 1,y - 1))
  width[x-1] += 1
  height[y-1] += 1

indexW = [i for i, v in enumerate(width) if v == max(width)]
indexH = [i for i, v in enumerate(height) if v == max(height)]

maxW = max(width)
maxH = max(height)

ans = maxW + maxH 

#それぞれ列と行の最大値の中から適当に１つずつ列と行を選ぶ
tmpX = indexW[0]
tmpY = indexH[0]

#HeightとWidthのそれぞれの最大値の点(x, y)に爆弾がない場合があるかどうか
flag = 0

#print(f"maxW : {maxW}")
#print(f"maxH : {maxH}")
#print(f"set : {st}")
#print(f"indexH {indexH}")
#print(f"indexW {indexW}")

#Heightの最大値と、widthのそれぞれを全探索
for x in indexW:
  y = tmpY
  if not (x, y) in st:
    flag = 1
    break


for y in indexH:
  x = tmpX
  if not (x, y) in st:
    flag = 1
    break

if flag == 1:
  print(ans)
else:
  print(ans - 1);

Submission status: Time Limit Exceeded

Solution code:
h,w,m = map(int,input().split())
row = [0]*(h+1)
col = [0]*(w+1)
bombs = set([])
for i in range(m):
  a,b = map(int,input().split())
  row[a] += 1
  col[b] += 1
  bombs.add((a,b))
r,c = max(row),max(col)
for i in range(1,h+1):
  if row[i]!=r:
    continue
  for j in range(1,w+1):
    if col[j]!=c:
      continue
    if (i,j) not in bombs:
      print(r+c)
      exit()
else:
  print(r+c-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, M = map(int, input().split())
bombs = []
for i in range(H):
    bombs.append([False] * W)
rows = []
for i in range(H):
    rows.append([i, 0])
cols = []
for i in range(W):
    cols.append([i, 0])
for i in range(M):
    y, x = map(lambda x: x - 1, map(int, input().split()))
    bombs[y][x] = True
    rows[y][1] += 1
    cols[x][1] += 1


rows = sorted(rows, key=lambda x: x[1], reverse=True)
cols = sorted(cols, key=lambda x: x[1], reverse=True)
answer = 0
for row in rows:
    a = cols[0][1] + row[1] - (1 if bombs[row[0]][cols[0][0]] else 0)
    if a > answer:
        answer = a
for col in cols:
    a = rows[0][1] + col[1] - (1 if bombs[rows[0][0]][col[0]] else 0)
    if a > answer:
        answer = a
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

H, W, M = map(int, input().split())
counterH = [0] * H
counterW = [0] * W
setHW = set({})
for _ in range(M):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    setHW.add((hi, wi))
    counterH[hi] += 1
    counterW[wi] += 1


set_max_h, set_max_w = set(), set()
max_h, max_w = -1, -1

for h in range(H):
    if counterH[h] > max_h:
        max_h = counterH[h]
        set_max_h = set({h})
    elif counterH[h] == max_h:
        set_max_h.add(h)

for w in range(W):
    if counterW[w] > max_w:
        max_w = counterW[w]
        set_max_w = set({w})
    elif counterW[w] == max_w:
        set_max_w.add(w)
    
def count(h, w):
    bomb = 0 if (h, w) not in setHW else -1
    bomb += counterH[h]
    bomb += counterW[w]
    return bomb

m = -1
for h in set_max_h:
    for w in range(W):
        m = max(m, count(h, w))
for w in set_max_w:
    for h in range(H):
        m = max(m, count(h, w))

print(m)

Submission status: Time Limit Exceeded

Solution code:
import math, sys

H,W,M=list(map(int, input().split()))
Bs=[]
#Map=[ [False for _ in range(W+1)] for _ in range(H+1)]

for _ in range(M):
    bh,bw=list(map(int, input().split()))
    #Map[bh][bw]=True
    Bs.append((bh,bw))
Hs=[0 for _ in range(H+1)]
Ws=[0 for _ in range(W+1)]

for each in Bs:
    hh,ww=each
    Hs[hh]+=1
    Ws[ww]+=1


hmax=max(Hs)
wmax=max(Ws)

hmax_list=[]
wmax_list=[]
for i in range(1,H+1):
    if Hs[i]==hmax:
        hmax_list.append(i)
for i in range(1,W+1):
    if Ws[i]==wmax:
        wmax_list.append(i)
ans=hmax+wmax
Bs.sort()
for hi in hmax_list:
    for wi in wmax_list:
        if (hi,wi) not in Bs:
            print(ans)
            sys.exit()
print(ans-1)