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: Wrong Answer

Solution code:
import collections

a = list(map(int,input().split()))
c = []
d = []
for i in range(a[2]):
    b = list(map(int,input().split()))
    c.append(b[0])
    d.append(b[1])

ans1 = 0
ans2 = 0

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

ans1 += gc
ans2 += hc
for i in range(a[2]):
    if c[i] == g:
        c[i] = -1
    if d[i] == h:
        d[i] = -1    

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

if g == -1:
    if gc == a[2]:
        gc = 0
    else:
        g = e.most_common()[1][0]
        gc = e.most_common()[1][1]
if h == -1:
    if hc == a[2]:
        hc = 0
    else:
        h = f.most_common()[1][0]
        hc = f.most_common()[1][1]

ans1 += gc
ans2 += hc
if ans1 > ans2:
    print(str(ans1))
else:
    print(str(ans2))

Submission status: Wrong Answer

Solution code:
import collections

a = list(map(int,input().split()))
c = []
d = []
for i in range(a[2]):
    b = list(map(int,input().split()))
    c.append(b[0])
    d.append(b[1])

ans1 = 0
ans2 = 0

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

ans1 += gc
ans2 += hc
print(ans1)
print(ans2)
for i in range(a[2]):
    if c[i] == g:
        c[i] = -1
    if d[i] == h:
        d[i] = -1    

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

if g == -1:
    if gc == a[2]:
        gc = 0
    else:
        g = e.most_common()[1][0]
        gc = e.most_common()[1][1]
if h == -1:
    if hc == a[2]:
        hc = 0
    else:
        h = f.most_common()[1][0]
        hc = f.most_common()[1][1]
        print(h)
        print(hc)

ans1 += gc
ans2 += hc
print(ans1)
print(ans2)
if ans1 > ans2:
    print(str(ans1))
else:
    print(str(ans2))

Submission status: Wrong Answer

Solution code:
from random import randint
from collections import defaultdict
#from numba import njit
import numpy as np


#@njit
def f(h,w,m,ins):
    #b = np.zeros((h,w),dtype=np.int8)
    yp = np.zeros(h,dtype=np.int)
    xp = np.zeros(w,dtype=np.int)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    for hi,wi in ins:
        d[hi-1][wi-1] = True
        yp[hi-1] += 1
        xp[wi-1] += 1
    yps = np.argsort(yp)[::-1]
    xps = np.argsort(xp)[::-1]
    y = yp[yps[0]]
    ans += y
    for xpsi in xps:
        a = y
        a += xp[xpsi]
        a -= d[yps[0]][xp[xpsi]]
        ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans = f(h,w,m,ins)
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections

a = list(map(int,input().split()))
c = []
d = []
for i in range(a[2]):
    b = list(map(int,input().split()))
    c.append(b[0])
    d.append(b[1])

ans1 = 0
ans2 = 0

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

ans1 += gc
ans2 += hc

for i in range(a[2]):
    if c[i] == g:
        c[i] = -1
    if d[i] == h:
        d[i] = -1    

e = collections.Counter(c)
f = collections.Counter(d)
g = e.most_common()[0][0]
gc = e.most_common()[0][1]
h = f.most_common()[0][0]
hc = f.most_common()[0][1]

if g == '-1':
    if gc == a[2]:
        gc = 0
    else:
        g = e.most_common()[1][0]
        gc = e.most_common()[1][1]
if h == '-1':
    if hc == a[2]:
        hc = 0
    else:
        h = f.most_common()[1][0]
        hc = f.most_common()[1][1]

ans1 += gc
ans2 += hc

if ans1 > ans2:
    print(str(ans1))
else:
    print(str(ans2))

Submission status: Wrong Answer

Solution code:
from collections import Counter
ans = 0
H, W, M = map(int, input().split())
HW = set()
Hlist, Wlist = [], []
for _ in range(M):
    h, w = map(int, input().split())
    Hlist.append(h)
    Wlist.append(w)
    HW.add((h,w))

cntH = Counter(Hlist)
cntW = Counter(Wlist)

maxhk, maxhv = cntH.most_common()[0]
ans = max(ans, maxhv)
for i in range(1,1+W):
    tmp = cntW[i]
    if (maxhk, i) in HW:
        tmp -= 1
    ans = max(ans, tmp+maxhv)
maxwk, maxwv = cntW.most_common()[0]
ans = max(ans, maxwk)
for i in range(1,1+H):
    tmp = cntH[i]
    if (i, maxwk) in HW:
        tmp -= 1
    ans = max(ans, tmp+maxwv)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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

Bom_list = list()
Y_list = list()
X_list = list()

for _ in range(M):
    Bom = list(map(int,input().split()))
    Bom_list.append(Bom)
    Y_list.append(Bom[0])
    X_list.append(Bom[1])

Y_counter = collections.Counter(Y_list)
X_counter = collections.Counter(X_list)

set_Y = list(set(Y_list))
set_X = list(set(X_list))
len_set_Y = len(set_Y)
len_set_X = len(set_X)

max_Y_num = 0 
max_X_num = 0
max_Y_list = list()
max_X_list = list()


for i in range(len_set_Y):
    if max_Y_num < Y_counter[set_Y[i]]:
        max_Y_num = Y_counter[set_Y[i]]
        max_Y_list.append(set_Y[i])

for i in range(len_set_X):
     if max_X_num < X_counter[set_X[i]]:
        max_X_num = X_counter[set_X[i]]
        max_X_list.append(set_X[i])

# for i in range(len_set_Y):
#     if max_Y_num == Y_counter[set_Y[i]]:
#         max_Y_list.append(set_Y[i])

# for i in range(len_set_X):
#      if max_X_num == X_counter[set_X[i]]:
#          max_X_list.append(set_X[i])

ans = 0

for i in max_Y_list:
    for j in max_X_list:
        if [i,j] in Bom_list:
            ans = max_Y_num + max_X_num - 1
        else:
            ans = max_Y_num + max_X_num
            print(ans)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
HW = set()
Hlist, Wlist = [], []
for _ in range(M):
    h, w = map(int, input().split())
    Hlist.append(h)
    Wlist.append(w)
    HW.add((h,w))

cntH = Counter(Hlist)
cntW = Counter(Wlist)
flg = False
if cntH.most_common()[0][1] < cntW.most_common()[0][1]:
    cntH, cntW = cntW, cntH
    flg = True


maxhk, maxhv = cntH.most_common()[0]
ans = maxhv
for i in range(1,1+W):
    tmp = cntW[i]
    if flg:
        if (i, maxhk) in HW:
            tmp -= 1
    else:
        if (maxhk, i) in HW:
            tmp -= 1
    ans = max(ans, tmp+maxhv)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
H, W, M = map(int, input().split())
HW = set()
Hlist, Wlist = [], []
for _ in range(M):
    h, w = map(int, input().split())
    Hlist.append(h)
    Wlist.append(w)
    HW.add((h,w))

cntH = Counter(Hlist)
cntW = Counter(Wlist)

if cntH.most_common()[0][1] < cntW.most_common()[0][1]:
    cntH, cntW = cntW, cntH


maxhk, maxhv = cntH.most_common()[0]
ans = maxhv
for i in range(1,1+W):
    tmp = cntW[i]
    if (maxhk, i) in HW:
        tmp -= 1
    ans = max(ans, tmp+maxhv)
print(ans)

Submission status: Wrong Answer

Solution code:
# E
from collections import Counter

H,W,M=map(int,input().split())
h,w=[0]*M,[0]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())

hm,wm=Counter(h).most_common()[0][1],Counter(w).most_common()[0][1]
if (hm,wm) in [(h[i],w[i]) for i in range(M)]:
    print(hm+wm-1)
else:
    print(hm+wm)

Submission status: Wrong Answer

Solution code:
from random import randint
from collections import defaultdict
from numba import njit
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    #b = np.zeros((h,w),dtype=np.int8)
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    #for i in range(m):
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        d[hi-1][wi-1] = True
        #b[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
        
    y = yp[yps[0]]
    ans += y[0]
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        #print(a,xpsi,d[yps[0]][xpsi])
        a -= d[yps[0]][xp[xpsi,1]]
        ans = max(ans,a)
    #print(y)
    #print(b)
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Wrong Answer

Solution code:
from random import randint
from collections import defaultdict
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    #b = np.zeros((h,w),dtype=np.int8)
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    d = defaultdict(lambda: defaultdict(bool))
    #for i in range(m):
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        d[hi-1][wi-1] = True
        #b[hi-1][wi-1] = True
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
        
    y = yp[yps[0]]
    ans += y[0]
    for xpsi in xps:
        a = y[0]
        a += xp[xpsi,0]
        #print(a,xpsi,d[yps[0]][xpsi])
        a -= d[yps[0]][xpsi]
        ans = max(ans,a)
    #print(y)
    #print(b)
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W,M = LMIIS()
    targets_row = []
    targets_column = []
    c2r = defaultdict(lambda : defaultdict(bool))
    for i in range(M):
        column,row = LMIIS()
        targets_row.append(row)
        targets_column.append(column)
        c2r[column][row] = True

    common_columns = Counter(targets_column).most_common()
    common_rows = Counter(targets_row).most_common()
    ans = common_columns[0][1] + common_rows[0][1]
    dbg(common_columns[0][0],common_rows[0][0])
    if c2r[common_columns[0][0]][common_rows[0][0]]:
        ans -= 1

    print(ans)
    
    

    
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
k = 0
while k < H:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while k < W:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)

if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  bomb = deque(bomb)
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  kouho.sort()
  kouho = deque(kouho)
  B = bomb.popleft()
  K = kouho.popleft()
  while True:
    if B > K:
      ans += 1
      break
    elif B == K:
      if len(kouho) == 0:
        break
      else:
        K = kouho.popleft()
    else:
      if len(bomb) == 0:
        break
      else:
        B = bomb.popleft()
print(ans)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
h = [0] * (H + 1)
w = [0] * (W + 1)
bombs = [[]] * (H + 1)
for i in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    bombs[x].append(y)

hmax = max(h)
wmax = max(w)
hsrch = []
wsrch = []
for i in range(len(h)):
    if h[i] == hmax:
        hsrch.append(i)
for i in range(len(w)):
    if w[i] == wmax:
        wsrch.append(i)

ans = 0
max = 0
for x in hsrch:
    for y in wsrch: 
        ans = h[x] + w[y]
        if ans > max:
            max = ans - 1 if y in bombs[x] else ans

print(max)

Submission status: Wrong Answer

Solution code:
import collections

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

Bom_list = list()
Y_list = list()
X_list = list()

for _ in range(M):
    Bom = list(map(int,input().split()))
    Bom_list.append(Bom)
    Y_list.append(Bom[0])
    X_list.append(Bom[1])

Y_counter = collections.Counter(Y_list)
X_counter = collections.Counter(X_list)

set_Y = list(set(Y_list))
set_X = list(set(X_list))
len_set_Y = len(set_Y)
len_set_X = len(set_X)

max_Y_num = 0 
max_X_num = 0

for i in range(len_set_Y):
    if max_Y_num < Y_counter[set_Y[i]]:
        max_Y_num = Y_counter[set_Y[i]]
    
for i in range(len_set_X):
     if max_X_num < X_counter[set_X[i]]:
         max_X_num = X_counter[set_X[i]]

max_Y_list = list()
max_X_list = list()

for i in range(len_set_Y):
    if max_Y_num == Y_counter[set_Y[i]]:
        max_Y_list.append(set_Y[i])

for i in range(len_set_X):
     if max_X_num == X_counter[set_X[i]]:
         max_X_list.append(set_X[i])

for i in max_Y_list:
    for j in max_X_list:
        if [i,j] in Bom_list:
            ans = max_Y_num + max_X_num - 1
        else:
            ans = max_Y_num + max_X_num
            break
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = set()
    row = [0] * h
    col = [0] * w
    for _ in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target.add((hi, wi))
        row[hi] += 1
        col[wi] += 1
    row_max = max(row)
    r = [i for i in range(h) if row[i] == row_max]
    col_max = max(col)
    ans = row_max + col_max - 1
    c = [i for i in range(w) if col[i] == col_max]
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w, m = map(int, read().split())
    target = [(0, 0) for _ in range(m)]
    row = [0] * h
    col = [0] * w
    for i in range(m):
        hi, wi = [int(i) - 1 for i in input().split()]
        target[i] = (hi, wi)
        row[hi] += 1
        col[wi] += 1
    row_max = max(row)
    r = [i for i in range(h) if row[i] == row_max]
    col_max = max(col)
    ans = row_max + col_max - 1
    c = [i for i in range(w) if col[i] == col_max]
    for ri in r:
        for ci in c:
            if (ri, ci) not in target:
                ans += 1
                break
    print(ans)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            flag = 1
            break

if flag == 0:
    print(H_max + W_max -1)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
            print(s)
            break
if s == max_h_items[0][1] + max_w_items[0][1] - 1:
    print(s)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]
print(m)
for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1] - 1
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) not in m:
            s = mh[1]+mw[1]
print(s)

Submission status: Wrong Answer

Solution code:
H, W, M = map(int, input().split())
h_dic, w_dic = {}, {}
m = set()
for i in range(M):
    h_i, w_i = map(int, input().split())
    m.add((h_i, w_i))
    if h_i in h_dic:
        h_dic[h_i] += 1
    else:
        h_dic[h_i] = 1
    if w_i in w_dic:
        w_dic[w_i] += 1
    else:
        w_dic[w_i] = 1
        
max_h_items = [[0,0]]
max_w_items = [[0,0]]

for key, value in h_dic.items():
    if value > max_h_items[0][1]:
        max_h_items = [[key, value]]
    elif value == max_h_items[0][1]:
        max_h_items.append([key, value])
for key, value in w_dic.items():
    if value > max_w_items[0][1]:
        max_w_items = [[key, value]]
    elif value == max_w_items[0][1]:
        max_w_items.append([key, value])
s = max_h_items[0][1] + max_w_items[0][1]
for mh in max_h_items:
    for mw in max_w_items:
        if (mh[0], mw[0]) in m:
            s = mh[1]+mw[1]-1
print(s)

Submission status: Wrong Answer

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



g = []
g2 = []
cg2 = []
for _ in range(h):
	a = []
	for j in range(w):
		a.append(0)
	g.append(a)

for _ in range(m):
	x, y = list(map(int, input().split()))
	g[x-1][y-1] = 1

c = 0
r = 0
bx = 0
by = 0
for i, x in enumerate(g):
	if sum(x) > bx:
		bx = sum(x)
		r = i

new = g[:]
new.pop(r)
for i in range(len(g[0])):
	cg2.append([l[i] for l in new])
	g2.append([l[i] for l in g])

for i, x in enumerate(cg2):
	if sum(x) > by:
		by = sum(g2[i])
		c = i
print(bx+by-g[r][c])

Submission status: Wrong Answer

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

h_target = [0]*(H+1)
w_target = [0]*(W+1)
target = []

for _ in range(M):
    h,w = map(int,input().split())
    target.append((h,w))
    h_target[h] += 1
    w_target[w] += 1

max_h_target = max(h_target)
max_w_target = max(w_target)

flag = False # 爆破対象の座標以外で最適な地点があるかどうか

for i,j in target:
    if h_target[i] != max_h_target and w_target[j] != max_w_target:
        break
else:
    flag = True

if flag:
    print(max_h_target+max_w_target)
else:
    print(max_h_target+max_w_target-1)

Submission status: Wrong Answer

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



g = []
g2 = []
cg2 = []
for _ in range(h):
	a = []
	for j in range(w):
		a.append(0)
	g.append(a)

for _ in range(m):
	x, y = list(map(int, input().split()))
	g[x-1][y-1] = 1

c = 0
r = 0
bx = 0
by = 0
for i, x in enumerate(g):
	if sum(x) > bx:
		bx = sum(x)
		r = i

new = g[:]
new.pop(r)
for i in range(0, len(g[0])-1):
	test = [l[i] for l in new]
	cg2.append(test)
	test = [l[i] for l in g]
	g2.append(test)

for i, x in enumerate(cg2):
	if sum(x) > by:
		by = sum(x)
		c = i
print(bx+by-g[r][c])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m,k=map(int,input().split())
points=set()
row=defaultdict(int)
col=defaultdict(int)
for i in range(k):
    a,b=map(int,input().split())
    points.add((a,b))
    row[a]+=1
    col[b]+=1
m1=max(row.values())
m2=max(col.values())
l1=[]
l2=[]
for i in row:
    if row[i]==m1:
        l1.append(i)
for i in col:
    if col[i]==m2:
        l2.append(i)
ans=m2+m1-1
for i in l1:
    for j in l2:
        if (i,j) not in points:
            print(i,j)
            ans+=1
            print(ans)
            quit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m,k=map(int,input().split())
points=set()
row=defaultdict(int)
col=defaultdict(int)
for i in range(k):
    a,b=map(int,input().split())
    points.add((a,b))
    row[a]+=1
    col[b]+=1
m1=max(row.values())
m2=max(col.values())
l1=[]
l2=[]
for i in row:
    if i==m1:
        l1.append(i)
for i in col:
    if i==m2:
        l2.append(i)
ans=m2+m1-1
for i in l1:
    for j in l2:
        if (i,j) not in points:
            ans+=1
            print(ans)
            quit()
print(ans)

Submission status: Wrong Answer

Solution code:
from random import randint
from collections import defaultdict
import numpy as np

#h,w,m = map(int,input().split())
def f(h,w,m,ins):
    #h,w,m = map(int,input().split())
    #b = np.zeros((h,w),dtype=np.bool)
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0


    #for i in range(m):
    for hi,wi in ins:
        #hi,wi = map(int,input().split())
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    yps = np.argsort(yp[:,0])[::-1]
    xps = np.argsort(xp[:,0])[::-1]
    ans += yp[yps[0],0]+xp[xps[0],0]
    return ans

if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ans = f(h,w,m,[(randint(1,h),randint(1,w)) for i in range(m)])
        print(ans)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)

Submission status: Wrong Answer

Solution code:
H,W,M = map(int,input().split())
 
horizontal = [[i,0] for i in range(H)]
vertical = [[i,0] for i in range(W)]
table = {}
 
for i in range(M):
    h,w = map(int,input().split())
    h -= 1
    w -= 1
    table[(h,w)] = True
    vertical[w][1] += 1
    horizontal[h][1] += 1
 
vertical.sort(key=lambda x:-x[1])
horizontal.sort(key=lambda x:-x[1])
 
h_max = horizontal[0][1]
v_max = vertical[0][1]
    
for i in range(H):
    if horizontal[i][1]<h_max:
        break
for j in range(W):
    if vertical[j][1]<v_max:
        break
 
flag = False
for h in horizontal[:i]:
    for v in vertical[:j]:
        if table.get((h[0],v[0]))==None:
            flag = True
            break
    if flag:
        break
 
if flag:
    print(h_max+v_max)
else:
    print(h_max+v_max-1)

Submission status: Wrong Answer

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

horizontal = [[i,0] for i in range(H)]
vertical = [[i,0] for i in range(W)]
table = {}

for i in range(M):
    h,w = map(int,input().split())
    h -= 1
    w -= 1
    table[(h,w)] = True
    vertical[w][1] += 1
    horizontal[h][1] += 1

vertical.sort(key=lambda x:-x[1])
horizontal.sort(key = lambda x:-x[1])

h_max = horizontal[0][1]
v_max = vertical[0][1]
    
for i in range(H):
    if horizontal[i][1]<h_max:
        break
for j in range(W):
    if vertical[j][1]<v_max:
        break

flag = False
for h in horizontal[:i]:
    for v in vertical[:j]:
        if not table.get((h[0],v[0])):
            flag = True
            break
    if flag:
        break

if flag:
    print(h_max+v_max)
else:
    print(h_max+v_max-1)

Submission status: Wrong Answer

Solution code:
H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
s=[[] for _ in range(H)]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  s[h-1].append(w-1)
 
qh=[]
qw=[]
maxh=max(sumh)
maxw=max(sumw)
qh=(i for i,x in enumerate(sumh) if x==maxh)
qw=(i for i,x in enumerate(sumw) if x==maxw)

for i in qh:
  for j in qw:
    if j not in s[i]:
      print(maxh+maxw)
      exit()
 
print(maxh+maxw-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush


h,w,m=[int(x) for x in input().split()]

#defaultdictにすることにより後に使うmax関数のコストを削減
hcnt=defaultdict(int)
wcnt=defaultdict(int)
#存在チェックのアクセスがリストで持たせるより高速
#リストは突っ込めないので注意(hashabeのみOK)
bomb=defaultdict()
#O(H)
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb[(hi,wi)]=True

#O(H)
hmax=max(hcnt.values())
wmax=max(wcnt.values())

#O(H)
hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

print(bomb)

#O(H**2)
ofst=-1
for i in hidx:
    for j in widx:
        if not bomb.get((i,j)):
            ofst=0
            break
                
print(hmax+wmax+ofst)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush


h,w,m=[int(x) for x in input().split()]

#defaultdictにすることにより後に使うmax関数のコストを削減
hcnt=defaultdict(int)
wcnt=defaultdict(int)
#存在チェックのアクセスがリストで持たせるより高速
#リストは突っ込めないので注意(hashabeのみOK)
bomb=defaultdict()
#O(H)
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb[(hi,wi)]=True

#O(H)
hmax=max(hcnt.values())
wmax=max(wcnt.values())

#O(H)
hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

#O(H**2)
ofst=-1
for i in hidx:
    for j in widx:
        if not bomb[(hi,wi)]:
            ofst=0
            break
                
print(hmax+wmax+ofst)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict
H,W,M=map(int,input().split())
Bomb_ls=set()
R=defaultdict(int)
C=defaultdict(int)
for i in range(M):
  X,Y=[int(x) for x in input().split()]
  Bomb_ls.add((X-1,Y-1))
  R[X-1]+=1
  C[Y-1]+=1
R_max=[i for i, x in enumerate(R) if x == max(R)]
C_max=[i for i, x in enumerate(C) if x == max(C)]
if len(R_max)*len(C_max)>M:
  print(max(R)+max(C))
else:
  score=-1
  for r in R_max:
    for c in C_max:
      if not (r,c) in Bomb_ls:
        score=0
        break
  print(max(R)+max(C)+score)

Submission status: Wrong Answer

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

for i in range(m):
    hi, wi = map(lambda x:int(x) - 1, input().split())
    mh[hi] += 1
    mw[wi] += 1 
    a.append((hi, wi))

ans = max(mh) + max(mw)
mh_ = [i for i, v in enumerate(mh) if v == max(mh)]
mw_ = [i for i, v in enumerate(mw) if v == max(mw)]

for i in mh_:
    for j in mw_:
        if (i, j) in a:
            print(ans-1)
            exit()
print(ans)

Submission status: Wrong Answer

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

bom = set()
for i in range(m):
    x,y = map(int,input().split())
    x-=1
    y-=1
    hb[x][0] += 1
    wb[y][0] += 1
    bom.add(tuple([x,y]))

ans = 0
hb.sort(reverse=True)
wb.sort(reverse=True)

for i,x in hb:
    for j,y in wb:
        a = i+j
        if (x,y) in bom:
            a -= 1
        if ans<a:
            ans = a
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,m = map(int,input().split())
hb = [0]*h
wb = [0]*w
bom = set()
mh = mx = mw = my = 0
for i in range(m):
    x,y = map(int,input().split())
    hb[x-1] += 1
    wb[y-1] += 1
    if mh<hb[x-1]:
        mh = hb[x-1]
        mx = x-1
    if mw<wb[y-1]:
        mw = wb[y-1]
        my = y-1
    bom.add(tuple([x-1,y-1]))
ans = hb[mx]+wb[my]
if (mx,my) in bom:
    ans -= 1
print(ans)

Submission status: Wrong Answer

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

ListH = [0 for i in range(H)]
ListW = [0 for i in range(W)]

# 二次元グリッドのサイズの宣言
S = [[0 for i in range(W)] for j in range(H) ]

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

maxH = max(ListH)
maxW = max(ListW)

maxPH = ListH.index(maxH)
maxPW = ListW.index(maxW)

if S[maxPH][maxPW] == 1:
  print(maxH  + maxW - 1)
else:
  print(maxH  + maxW)

Submission status: Wrong Answer

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

ListH = [0 for i in range(H)]
ListW = [0 for i in range(W)]

# 二次元グリッドのサイズの宣言
S = [[0 for i in range(W)] for j in range(H) ]

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

maxH = max(ListH)
maxW = max(ListW)

maxPH = ListH.index(maxH)
maxPW = ListW.index(maxW)

if S[maxPH][maxPW] == 1:
  print(ListH[0] + ListW[0] - 1)
else:
  print(ListH[0] + ListW[0])