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: Runtime Error

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(cha)-1):
    if cwa[i] == cwa[i+1]:
        wli.append(int(wa[i+1]))
    else:
        break

if len(hli)*len(wli) <= 10**7:
    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: Runtime Error

Solution code:
#import numpy as np
import collections
#import math




f = open('./input_E.txt')

H,W,M=map(int, f.readline().split())
bakuha = []
bakuha_H=[]
bakuha_W=[]
for i in range(M):
    hh,ww=map(int, f.readline().split())
    bakuha_H.append(hh)
    bakuha_W.append(ww)
    bakuha.append([hh,ww])




#H,W,M=map(int, input().split())
#bakuha = []
#bakuha_H=[]
#bakuha_W=[]
#for i in range(M):
#    hh,ww=map(int, input().split())
#    bakuha_H.append(hh)
#    bakuha_W.append(ww)
#    bakuha.append([hh,ww])





count_H = collections.Counter(bakuha_H)
H_most = count_H.most_common()
H_most_num = H_most[0][1]

H_only_most = [x for x in H_most if x[1]==H_most_num]
H_kouho = [x[0] for x in H_only_most]


count_W = collections.Counter(bakuha_W)
W_most = count_W.most_common()
W_most_num = W_most[0][1]

W_only_most = [x for x in W_most if x[1]==W_most_num]
W_kouho = [x[0] for x in W_only_most]

ans = H_most_num + W_most_num



#爆破対称のある座標にしか置けなかったらマイナス1
#H_kouho_index = [i for i in range(M) if bakuha_H[i] in H_kouho]
#W_kouho_index = [i for i in range(M) if bakuha_W[i] in W_kouho]
#
#ans_minus=True
#if len(H_kouho_index) <= len(W_kouho_index):
#    for h_index in H_kouho_index:
#        if h_index not in W_kouho_index:
#            ans_minus = False
#            break
#else:
#    for w_index in W_kouho_index:
#        if w_index not in H_kouho_index:
#            ans_minus = False
#            break
#if H_kouho_index == W_kouho_index:

#if ans_minus:
#    ans-=1

#bakuha_array = np.array(bakuha)
#for h_kouho in H_kouho:
#    for w_kouho in W_kouho:
#        bakuha_array = bakuha_array[bakuha_array[0]==h_kouho]
#
##    bakuha_array = bakuha_array[bakuha_array[1]==w_kouho]


#ryouhou = 0
#for bb in bakuha:
#    x,y = bb
#    if x in H_kouho and y in W_kouho:
#        ryouhou+=1
#
#h_by_w = len(H_kouho)*len(W_kouho)
#
#if ryouhou == h_by_w:
#    ans -= 1
    

print(ans)

Submission status: Runtime Error

Solution code:
h, w, n = [int(i) for i in input().split()]
import numpy as np
maps = np.zeros((h, w))
for _ in range(n):
    tmp = [(int(i) -1) for i in input().split()]
    maps[tmp[0], tmp[1]] = 1
sum_row = [np.sum(maps[i, :]) for i in range(h)]
arg_max = np.argmax(sum_row)
for i in range(w):
    tmp = np.sum(maps[:, i])
    if int(maps[arg_max, i]) == 1:
        tmp -= 1
print(int(max(sum_row) + tmp))

Submission status: Runtime Error

Solution code:
import numpy as np
h,w,m=map(int, input().split())
a = np.zeros((h,w))
ans=0

for i in range(m):
    x,y=map(int, input().split())
    a[x-1,y-1]=1
    
c = a.sum(axis=0)
r = a.sum(axis=1)
cm = max(c)
rm = max(r)
ci = [i for i, x in enumerate(c) if x == cm]
ri = [i for i, x in enumerate(r) if x == rm]
ans = cm + rm

print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy
h,w,m = map(int,input().split())
hight = [0]*h
width = [0]*w
matrix =[0]*w
for i in range(w):
    matrix[i] = [0]*h
for i in range(m):
    hi,wi = map(int,input().split())
    hight[hi-1]+=1
    width[wi-1]+=1
    matrix[wi-1][hi-1] += 1
# print(matrix)
max_vh = numpy.argmax(hight)
max_vw = numpy.argmax(width)
print(hight[max_vh]+width[max_vh]-matrix[max_vw][max_vh])

Submission status: Runtime Error

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

cnt = 0
h_p = collections.Counter(w).most_common()
h_s = h_p[0][0]

for i in range(M):
  if h[i] == h_s:
    w[i] = 0
    cnt += 1

while 0 in w:
  w.remove(0)

w_p = collections.Counter(w).most_common()
w_s_1 = w_p[0][0]

for i in range(len(w)):
  if w[i] == w_s_1:
    cnt += 1
    
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W, M = map(int, input().split())
glt = np.zeros((H, W))

for i in range(M):
    h, w = map(int, input().split())
    glt[h-1][w-1] = 1
    
cnt =0
max_bomb = 0
retsu = np.sum(glt, axis=0)
gyo = np.sum(glt, axis=1)


for i in range(H-1):
    for j in range(W-1):
        if retsu[i+1] + gyo[j+1] > retsu[i] + gyo[j]:
            max_bomb = retsu[i+1] + gyo[j+1]
            
print(int(max_bomb))

Submission status: Runtime Error

Solution code:
h,w,m  = list(map(int, input().strip().split()))
a=[0]*m
b=[0]*m
grid = []
for i in range(m):
    array = list(map(int, input().strip().split()))
    grid.append(array)
for i in range(m):
    a[i]=grid[i][0]
    b[i]=grid[i][1]
H=[0]*h
W=[0]*w
for i in range(h):
    H[i]=a.count(i+1)
for i in range(h):
    W[i]=b.count(i+1)
kosuu= []
for i in range(h):
    for j in range(w):
        if [i+1,j+1]in grid:
            kosuu.append(H[i]+W[j]-1)
        else:
            kosuu.append(H[i]+W[j])

print(max(kosuu))

Submission status: Runtime Error

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 = [0] * 2 for i in range(M)]
for i in range(M):
    nyuuryoku[i] = (h[i],w[i])
nyuuryoku_set = set(nyuuryoku)

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: Runtime Error

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

import numpy as np

area = np.zeros((H, W), int)

for _ in range(M):
    y, x = map(int, input().split(" "))
    area[y-1][x-1] = 1
    
W_sum_ = area.sum(axis = 1)
H_sum_ = area.sum(axis = 0)

y_index = np.where(W_sum_ == W_sum_.max())[0]
x_index = np.where(H_sum_ == H_sum_.max())[0]

max_sum = 0
x_max = y_max = 0

for y in y_index:
    for x in x_index:
        sum_ = H_sum_[x] + W_sum_[y]
        if area[y][x] == 1:
            sum_ -= 1
        if sum_ > max_sum:
            max_sum = sum_
            x_max = x
            y_max = y
            
print(max_sum)

Submission status: Runtime Error

Solution code:
h,w,m=map(int,input().split())
s=[0]*m
st=[0]*m
t=[0]*m
tt=[0]*m
for i in range(m):
  sm,tm=map(int,input().split())
  s[i]=sm
  st[i]=sm
  t[i]=tm
  tt[i]=tm
  
import statistics
temp=statistics.mode(s)
ans1=s.count(temp)
for i in range(m):
  if s[i]==temp:
    tt[i]=999999999999999999
while 999999999999999999 in tt:tt.remove(999999999999999999)
temp=statistics.mode(tt)
ans1=ans1+tt.count(temp)

temp=statistics.mode(t)
ans2=t.count(temp)
for i in range(m):
  if t[i]==temp:
    st[i]=999999999999999999
while 999999999999999999 in st:st.remove(999999999999999999)
temp=statistics.mode(st)
ans2=ans2+st.count(temp)

print(max(ans1,ans2))

Submission status: Runtime Error

Solution code:
#n = int(input())
#a = list(map(int, input().split()))
h, w, m = map(int, input().split())
listh = [0] * m
listw = [0] * m
lista = [0] * (m+1)
listb = [0] * (m+1)

for i in range(m):
    listh[i], listw[i] = map(int, input().split())
p = -1
q = -1
r = [0]
s = [0]
for i in range(1,h+1):
  lista[i] = listh.count(i)
  if p < lista[i]:
    p = lista[i]
    r = [0]
    r[0] = i
  if p == lista[i]:
    r.append(i)

for i in range(1,w+1):
  listb[i] = listw.count(i)
  if q < listb[i]:
    q = listb[i]
    s = [0]
    s[0] = i
  if q == listb[i]:
    s.append(i)
#print(p)
#print(q)
#p = max(lista)
#q = max(listb)
ans = 1
#r = [i for i, v in enumerate(lista) if v == p]
#s = [i for i, v in enumerate(listb) if v == q]
for i in range(len(r)):
  for j in range(len(s)):
    for k in range(m):
      if listh[k] == r[i] and listw[k] == s[j]:
        break
      if k == m-1:
        ans = 0
print(p+q-ans)

Submission status: Runtime Error

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

lh = []
lw = []

for i in range(m):
  h1,w1 = map(int, input().split())
  lh.append(h1)
  lw.append(w1)

if h == 1 or w == 1:
  print(m)
else:
  from collections import Counter as co
  ch=co(lh).most_common()

  tmp = ch[0][0]
  lh_c = [i for i, x in enumerate(lh) if x == tmp]
  for j in sorted(lh_c, reverse=True):
    lw.pop(j)
  cw = co(lw).most_common()
  ans = ch[0][1]+cw[0][1]

  print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, M = map(int, input().split())
h_t = [0]*H
w_t = [0]*W
t = np.zeros((H, W))
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, v in enumerate(h_t) if v == h_max]
w_max = max(w_t)
w_max_list = [i for i, v in enumerate(w_t) if v == 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: Runtime Error

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

h_list = []
w_list = []
hw_list = []

start_time = time.time()

for m in range(M):
    h_buf, w_buf = map(int, input().split())
    h_list.append(h_buf)
    w_list.append(w_buf)
    hw_list.append([h_buf, w_buf])

#print(time.time()-start_time)
h_c = collections.Counter(h_list)
w_c = collections.Counter(w_list)
h_c_list = h_c.most_common()
w_c_list = w_c.most_common()
#print(time.time()-start_time)

M = 0
count_h = 0
count_w = 0
M_j = 0
finish = 0

for k1, l in enumerate(h_c_list):
    if k1 > 100: break
    if (count_h > l[1])|(finish == 1): break
    count_h = l[1]
    i = l[0]
    M_i = count_h
    for k2, s in enumerate(w_c_list):
        if k2 > 100: break
        if (count_w > s[1])|(finish == 1): break
        count_w = s[1]
        j = s[0]
        M_buf = count_w
        #print(time.time()-start_time)
        if [i,j] in hw_list:
            M_buf -= 1
        else:
            finish = 1
        if M_buf>M_j:
            M_j = M_buf

print(M_i + M_j)

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline

def main():
    H, W, M = map(int, readline().rstrip().split())
    HW = [[0] * (W + 1) for _ in range(H + 1)]
    HS = set()
    WS = set()
    for _ in range(M):
        h, w = map(int, readline().rstrip().split())
        HW[h][w] = 1
        HW[h][0] += 1
        HS.add(h)
        HW[0][w] += 1
        WS.add(w)

    ans = 0
    for h in HS:
        for w in WS:
            tmp = HW[h][0] + HW[0][w]
            if HW[h][w] == 1:
                tmp -= 1
            ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

H=[0]*h
W=[0]*w
HW=[[False]*w for i in range(h)]
for mine in M:
    a=mine[0]-1
    b=mine[1]-1
    H[a]+=1
    W[b]+=1
    HW[a][b]=True

maxh=max(H)
maxw=max(W)

maxhindex = []
maxwindex = []

for i in range(h):
    if H[i]==maxh:
        maxhindex.append(i)
for i in range(w):
    if W[i]==maxw:
        maxwindex.append(i)

end=0

for i in maxhindex:
    for j in maxwindex:
        if HW[i][j]==False:
            end=1
            break
        else:
            continue
        break

ans=maxh+maxw
if end==0:
    ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前
sort()
sorted(reverse=true)
配列の初期化
配列名=[a]*n+[b]*m
Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys

d = [int(s) for s in stdin.readline().rstrip().split()]
h = d[0]
w = d[1]
m = d[2]
hCount = [0]*h
wCount = [0]*w
poss = [[0] * w for i in range(h)]
for el in range(m):
    pos = [int(s) for s in stdin.readline().rstrip().split()]
    hCount[pos[0]-1] += 1
    wCount[pos[1]-1] += 1
    poss[pos[0]-1][pos[1]-1] = 1
hPos = -1
value = -1
count = 0
for el in hCount:
    if value < el:
        value = el
        hPos = count
    count += 1
wPos = -1
count = 0
for el in wCount:
    if value < el:
        value = el
        wPos = count
    count += 1
if wPos != -1:
    line = []
    for el in poss:
        line.append(el[wPos])
    count = 0
    for el in line:
        hCount[count] -= el
        count += 1
    hValue = 0
    hPos = 0
    count = 0
    for el in hCount:
        if hValue < el:
            hValue = el
            hPos = count
        count += 1
    print(value+hValue)
else:
    line = poss[hPos]
    count = 0
    for el in line:
        wCount[count] -= el
        count += 1
    wValue = 0
    wPos = 0
    count = 0
    for el in wCount:
        if wValue < el:
            wValue = el
            wPos = count
        count += 1
    print(value+wValue)

Submission status: Runtime Error

Solution code:
import bisect
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    wlis = sorted(havew[hs[0]])
    for ws in dicwi:
        if ws[1] != wmax:
            break
        idx = bisect.bisect_left(wlis, ws[0])
        if ws[0] != wlis[idx]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

Submission status: Runtime Error

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

map_ = [[0]*W for i in range(H)]
for i in range(M):
  h, w = list(map(int, input().split()))
  map_[h - 1][w - 1] = 1
#print(map_)
cnt_h = [0] * W
cnt_w = [0] * H
for h in range(H):
  cnt_w[h] = sum(map_[h])
#  for w in range(W):
#    cnt_h[w] += map_[h][w] 
import numpy as np
map_T = (np.array(map_).T).tolist()
#print(map_T)
for w in range(W):
  cnt_h[w] = sum(map_T[w])
#print(cnt_h, cnt_w)

h_max = max(cnt_h)
w_max = max(cnt_w)
h_max_index = []
w_max_index = []

for i in range(W):
  if cnt_h[i] == h_max:
    h_max_index.append(i)
for i in range(H):
  if cnt_w[i] == w_max:
    w_max_index.append(i)
#print(h_max_index, w_max_index)

ans = h_max + w_max
flg = False

for i in range(len(h_max_index)):
  for j in range(len(w_max_index)):
    if map_[w_max_index[j]][h_max_index[i]] == 0:
      flg = not flg
      break
  else:
      continue
  break
if flg:
  print(ans)
else:
  print(ans - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
h, w, n = map(int, input().split())
b_lists = []
for i in range(n):
   b_lists.append(list(map(int, input().split())))

mx = np.zeros((h,w))
for b_list in b_lists:
  m_h = b_list[0] - 1
  m_w = b_list[1] - 1 
  mx[m_h, m_w] = 1

sum_max = 0
for i in range(h):
  for j in range(w):
    icount = list(map(str, list(mx[i,:]))).count("1.0")
    jcount = list(map(str, list(mx[:,j]))).count("1.0")
    if mx[i, j] == 1:
      tmp_max = icount + jcount - 1
    else:
      tmp_max = icount + jcount
    if sum_max < tmp_max:
      sum_max = tmp_max
print (sum_max)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

h,w,m=map(int,input().split())
l=[[0 for i in range(w+1)] for j in range(h+1)]
row=[0 for i in range(h+1)]
col=[0 for j in range(w+1)]

for i in range(m):
    x,y=map(int,input().split())
    l[x][y]=1
    row[x]+=1
    col[y]+=1
    
maxr=max(row)
maxc=max(col)
maxa=maxr+maxc
p=1
cl,rl=[],[]
for i in range(1,h+1):
    if(row[i]==maxr):rl.append(i)
for j in range(1,w+1):
    if(col[j]==maxc):cl.append(j)
    
for x in rl:
    for y in cl:
        if(l[x][y]==0):p=0;break
    if(p=0):break
    
print(maxa-p)

Submission status: Runtime Error

Solution code:
import numpy as np

HWM = [int(a) for a in input().split()]
H = HWM[0]
W = HWM[1]
M = HWM[2]

Bombs = np.array([[int(b) for b in input().split()] for l in range(M)])

npBombs = np.zeros((H,W))
for x,y in Bombs:
  npBombs[x-1,y-1] = 1

Hs = []
for x in range(H):
  s = int(np.sum(npBombs[x,::]))
  Hs.append(s)

Ws = []
for y in range(W):
  s = int(np.sum(npBombs[::, y]))
  Ws.append(s)

Hmax = int(max(Hs))
Wmax = int(max(Ws))

answer = Hmax + Wmax - 1
for x in range(H):
  for y in range(W):
    if Hs[x] == Hmax and Ws[y] == Wmax:
      if npBombs[x,y] == 0:
      	answer = Hmax + Wmax

print(int(answer))

Submission status: Runtime Error

Solution code:
import sys
h, w, m = map(int, input().split())
hlist = [0] * h
wlist = [0] * w
hwlist = [[0] * w for i in [1] * h]
for i in range(m):
    hi, wi = map(int, input().split())
    hlist[hi - 1] += 1
    wlist[wi - 1] += 1
    hwlist[hi - 1][wi - 1] = 1
maxh = max(hlist)
maxw = max(wlist)

hindex_num = [n for n, v in enumerate(hlist) if v == maxh]
windex_num = [n for n, v in enumerate(wlist) if v == maxw]

flag = 0
for hi in hindex_num:
    for wi in windex_num:
        if hwlist[hi][wi] == 0:
            print(maxh + maxw)
            flag = 1
            # return 0
            sys.exit()
if flag == 0:
    print(maxh + maxw - 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        if S[h][w]=="#":
            continue
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
H,W,M = map(int,input().split())
A = [[0]*W for y in range(H)]

for i in range(M):
    a,b=map(int,input().split())
    A[a-1][b-1] = 1

cntz = 0
cnto = 0
for i in range(H):
    for j in range(W):
        b = [k[j] for k in A]
        if A[i][j] == 0:
            cntz = max(sum(A[i]) +sum(b),cntz)
        else:
            cnto = max(sum(A[i]) +sum(b)-1,cnto)

print(max(cntz,cnto))

Submission status: Runtime Error

Solution code:
H,W,M= map(int,input().split())
S = [[0 for i in range(W)] for j in range(H) ]

for m in range(M):
  h, W = map(int,input().split())
  S[h-1][w-1] = "1"

maxcount = 0  
mpcount = 0  

for pi in range(0,H-1):
  for pj in range(0,W-1):
    
    tmpcount = 0
    
    for i in range(0,H-1):
      tmpcount = tmpcount + S[i][pj]
    for j in range(0,W-1):
      tmpcount = tmpcount + S[pi][j]
      
    if maxcount < tmpcount:
      maxcount = tmpcount
print(maxcount)

Submission status: Runtime Error

Solution code:
from abc import abstractmethod
from collections import defaultdict


class Edge:
    def __init__(self):
        self.flow = 0
        self.residual: Edge
        self.from_node = None
        self.to_node = None
        self.capacity = None

    @classmethod
    def by_nodes(cls, from_node, to_node, capacity):
        c = cls()
        c.connect(from_node, to_node, capacity)
        return c

    def connect(self, from_node, to_node, capacity):
        self.from_node = from_node
        self.to_node = to_node
        self.capacity = capacity

    def is_residual(self):
        return self.capacity == 0

    def remaining_capacity(self):
        return self.capacity - self.flow

    def augument(self, bottle_neck):
        self.flow += bottle_neck
        self.residual.flow -= bottle_neck

    def __repr__(self):
        return f"{self.from_node}-({self.flow}/{self.capacity})->{self.to_node}"


class NetworkFlowSolverBase:
    def __init__(self, n, s, t):
        self.visited_token = 1
        self.visited = defaultdict(int)
        self.solved = False
        self.max_flow = 0
        self.graph = defaultdict(list)
        # n: the number of nodes in the graph including s(src) and t(sink)
        self.n = n
        # s: the index of the src node
        self.s = s
        # t: the index of the sink node
        self.t = t

    def add_edge(self, from_node, to_node, capacity):
        assert capacity >= 0, f"forward-edge capacity must be >= 0: input={capacity}"
        e_f = Edge.by_nodes(from_node, to_node, capacity)
        e_b = Edge.by_nodes(to_node, from_node, 0)
        e_f.residual = e_b
        e_b.residual = e_f
        self.graph[from_node].append(e_f)
        self.graph[to_node].append(e_b)

    def get_graph(self):
        self.execute()
        return self.graph

    def get_max_flow(self):
        self.execute()
        return self.max_flow

    def execute(self):
        if self.solved:
            return
        self.solve()
        self.solved = True

    @abstractmethod
    def solve(self):
        pass


class FordFulkersonDfsSover(NetworkFlowSolverBase):
    def __init__(self, n, s, t):
        super().__init__(n, s, t)

    def solve(self):
        while True:
            f = self.dfs(self.s, float("inf"))
            self.visited_token += 1
            self.max_flow += f
            if f == 0:
                break

    def dfs(self, nd, flow):
        if nd == self.t:
            return flow
        self.visited[nd] = self.visited_token

        for e in self.graph[nd]:
            if (
                e.remaining_capacity() > 0
                and self.visited[e.to_node] != self.visited_token
            ):
                bottle_neck = self.dfs(e.to_node, min(flow, e.remaining_capacity()))
                if bottle_neck > 0:
                    e.augument(bottle_neck)
                    return bottle_neck
        return 0


if __name__ == "__main__":
    H, W, M, *subjects = map(int, open(0).read().split())
    S = H + W
    T = H + W + 1
    g = FordFulkersonDfsSover(H + W + 2, S, T)
    for i in range(H):
        g.add_edge(S, i, 1)
    for i in range(W):
        g.add_edge(i + H, T, 1)
    [g.add_edge(h - 1, w - 1 + H, 1) for h, w in zip(*[iter(subjects)] * 2)]
    print(g.get_max_flow() + 1)

Submission status: Runtime Error

Solution code:
import collections
H, M, W = map(int, input().split())
X = []
Y = []

for i in range(M):
    a, b = map(int, input().split())
    X.append(a)
    Y.append(b)
A = collections.Counter(X)
B = collections.Counter(Y)
cnt_x = A.most_common()[0][0]
cnt_y = B.most_common()[0][0]

x = A.most_common()[0][1]
y = B.most_common()[0][1]
print (cnt_x + cnt_y)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
H, W, M = map(int, input().split())

array = np.zeros([W, H])
for _ in range(M):
    i, j = map(int, input().split())
    array[j-1, i-1] = 1
    
# 行
sum_j = np.sum(array, axis = 0)
# 列
sum_i = np.sum(array, axis = 1)

i_list = np.where(sum_i == np.max(sum_i))[0]
j_list = np.where(sum_j == np.max(sum_j))[0]

flg = False
for i, j in itertools.product(i_list, j_list):
    if array[j, i] == 0:
        flg = True
        break

if flg:
    print(int(np.max(sum_i)+np.max(sum_j)))
else:
    print(int(np.max(sum_i)+np.max(sum_j)-1))

Submission status: Runtime Error

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,m=mp()
x=[]
y=[]
g=[[0]*(w+1) for i in range(h+1)]
for i in range(m):
    a,b=mp()
    g[a][b]=1
    x.append(a)
    y.append(b)
x=Counter(x)
y=Counter(y)
x=x.most_common()
y=y.most_common()


a=x[0][1]
b=y[0][1]
i=0
px=[]
py=[]
while x[i][1]==a:
    px.append(x[i][0])
    if i==len(x)-1:
        break
    i+=1
i=0
while y[i][1]==b:
    py.append(y[i][0])
    if i==len(y)-1:
        break
    i+=1

for i in px:
    for j in py:
        if g[i][j]==0:
            print(a+b)
            exit()
print(a+b-1)

Submission status: Runtime Error

Solution code:
import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object[h-1][w-1] = 1
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
print(ans)

Submission status: Runtime Error

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

maxh=maxw=0
qh=[]
qw=[]
for i in range(H):
  maxh=max(maxh, sumh[i][1])
for i in range(H):
  if maxh==sumh[i][1]:
    qh.append(i)

for i in range(W):
  maxw=max(maxw, sumw[i][1])
for i in range(W):
  if maxw==sumw[i][1]:
    qw.append(i)

for i in qh:
  for j in qw:
    if s[i][j]==0:
      print(maxh+maxw)
      exit()

print(maxh+maxw-1)

Submission status: Runtime Error

Solution code:
import random
h,w,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
exist = set()
tate = [[0,i] for i in range(h)]
yoko = [[0,i] for i in range(w)]

for y,x in lis:
    exist.add(format(y).zfill(6)+format(x).zfill(6))
    tate[y-1][0] += 1
    yoko[x-1][0] += 1

tate.sort(key=lambda x:x[1])
yoko.sort(key=lambda x:x[1])
tate.sort(key=lambda x:x[0],reverse=True)
yoko.sort(key=lambda x:x[0],reverse=True)

ans = tate[0][0]+yoko[0][0]-1
if h == 1 or w == 1:
    print(m)
    exit()

  # print(tate)
  # print(yoko)

i = 0
while i < h and i <= 1800:
    j = 0
    while j < w and j <= 1800:
        ans = max(ans,tate[i][0]+yoko[j][0]-bool(format(tate[i][1]+1).zfill(6)+format(yoko[j][1]+1).zfill(6) in exist))
        j += 1
        if yoko[0][0] > yoko[j][0] +1:
            break
    i += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

h, w, m = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(m)]

check = np.zeros((h, w))

for i,j in li:
    check[i-1, :] += 1
    check[:, j-1] += 1
    check[i-1, j-1] -= 1

idx = np.unravel_index(np.argmax(check), check.shape)
print(int(check[idx[0]][idx[1]]))

Submission status: Runtime Error

Solution code:
H,W,M=map(int,input().split())
A=[[0]*H]*M
Bomb_ls=[]
R=[0]*H
C=[0]*M
for i in range(M):
  X,Y=[int(x)-1 for x in input().split()]
  R[X]+=1
  C[Y]+=1
  Bomb_ls.append([X,Y])
score=0
for i in range(H):
  for j in range(Y):
    if not [i,j] in Bomb_ls:
      score=max(score,R[i]+C[j])
    else:
      score=max(score,R[i]+C[j]-1)
print(score)

Submission status: Runtime Error

Solution code:
H, W, N = map(int, input().split())
import numpy as np

M = np.zeros((H+1, W+1))
temp = np.zeros((2, H+W))
for i in range(N):
    a, b = list(map(int, input().split()))
    M[a][b] = 1
    temp[0][a] += 1
    temp[1][b] += 1

max_ = 0
for i in range(H):
    for j in range(W):
        if temp[0][i+1]+temp[1][j+1]-M[i+1][j+1] > max_:
            max_ = temp[0][i+1]+temp[1][j+1]-M[i+1][j+1]
print(int(max_))

Submission status: Runtime Error

Solution code:
from collections import Counter
h, w, m = map(int, input().split())
blist = [list(map(int, input().split())) for _ in range(m)]

ans_l = [0]*h
for i in range(h):
  ans = 0
  l = []
  for j in blist:
    if j[0] == i + 1:
      ans += 1
    else:
      l.append(j[1])
  l_c = Counter(l)
  ans += max(l_c.values())
  ans_l[i] = ans

print(max(ans_l))

Submission status: Runtime Error

Solution code:
import random
h,w,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
exist = set()
tate = [[0,i] for i in range(h)]
yoko = [[0,i] for i in range(w)]

for y,x in lis:
    exist.add(format(y).zfill(6)+format(x).zfill(6))
    tate[y-1][0] += 1
    yoko[x-1][0] += 1

tate.sort(key=lambda x:x[1])
yoko.sort(key=lambda x:x[1])
tate.sort(key=lambda x:x[0],reverse=True)
yoko.sort(key=lambda x:x[0],reverse=True)

ans = tate[0][0]+yoko[0][0]-1
if h == 1 or w == 1:
    print(m)
    exit()

  # print(tate)
  # print(yoko)

i = 0
while i < h and i <= 800:
    j = 0
    while j < w and j <= 800:
        ans = max(ans,tate[i][0]+yoko[j][0]-bool(format(tate[i][1]+1).zfill(6)+format(yoko[j][1]+1).zfill(6) in exist))
        j += 1
        if yoko[0][0] > yoko[j][0] +1:
            break
    i += 1
print(ans)